复盘携程0415笔试题
第二题
游游现在有一个公司,这个公司里有n个任务,每一个任务都有一个能力值和收益值,现在有m个工人,每一个工人都有一个能力值,对于每一个任务来说,只有这个人的能力值不低于该任务需要的能力值,才可以完成这个任务。假设多个工人可以完成同一个任务,收益为这个任务的收益值乘以这个任务完成的次数,现在想知道每一个工人最多只能安排一个任务的前提下,最大的收益值是多少?
输入描述
每一个文件输入第一行输入一个整数T($1 \leq T \leq 100$),代表有T组测试数据。
接下来T组,每一组第一行输入两个整数n,m($1 \leq n,m \leq 10^4$)
第二行输入n个整数,其中a[i]代表第i个任务所需要的的能力值
第三行输入n个整数,其中$p_i$($1 \leq p[i] \leq 10^5$)代表第i个任务的收益
第四行输入m个整数,其中$b_i$($1 \leq b[i] \leq 10^5$)代表第i个工人的能力数据保证同一个文件内n的总和不超过$10^5$,m的总和不超过$10^5$
数据保证同一个文件内n的总和不超过$10^5$,m的总和不超过$10^5$
输出描述
对于每一组测试数据,输出一个答案代表最大的收益。
示例
输入
1 |
输出
100 |
解释
对于样例:我们选择前两个工人做第二个任务,第三个工人和第四个工人做第三个任务,此时收益最大 |
思路
好像当时想的有点多了,不会出现能力要求高而收益低的任务,当时用的是动规。如果是这样话,可以使用贪心的方法解决,就是将任务和工人都按照能力值要求来排序,然后遍历到每个工人的时候,选择其能选择的收益最大的任务,不断累加收益,从局部最优扩展为整体最优。
代码如下
第三题
游游给定了两个正整数n,m,他希望能将n分解为恰好m个连续(排好序后满足后一项等于前一项加一)非负整数,使得这些数的和是n,他想知道能否办到,请你帮帮他吧。
连续的非负整数:即,如果将这些整数从小到大排好序后存入b数组,则第一项大于等于0,且对于任意i$(1 < i \leq m)$,都有$bi = b{i-1} + 1$
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T$(1 \leq T \leq 10^4)$代表数据组数,每组测试数据描述如下:
在单独的一行输入两个空格分割的正整数n,m$(1 \leq n \leq 10^{18}; 1 \leq m \leq 10^9)$,表示游游给定的正整数.
输出描述
对于每组测试数据:
如果可以将 n 分解为m个满足题意的非负整数,则在单独的一行输出”YES”,否则输出”NO”。(都不带双引号)