1. 题目
n个人，他们每个人需要独立做 m 份作业。 第 i 份作业需要花费 cost[i] 的时间。由于每个人的空闲时间不同，第 i 个人有 val[i] 的时间，这代表他做作业的总时间不会超过 val[i]。每个人都按照顺序，从1号作业开始，然后做2号，3号… 现在，你需要计算出他们最多花了多少的时间。
代码语言：javascript复制样例 1:
给定`cost=[1,2,3,5]`，`val=[6,10,4]`，返回`15`。
输入:
[1,2,3,5]
[6,10,4]
输出
15
解释:
第一个人可以完成1号作业，2号作业，3号作业，1 2 3<=6。
第二个人可以完成1号作业，2号作业，3号作业，无法完成4号作业，1 2 3<=10，1 2 3 5>10。
第三个人可以完成1号作业，2号作业，无法完成3号作业，1 2<=4，1 2 3>4。
1 2 3 1 2 3 1 2=15，返回15。
样例 2:
给定 `cost=[3,7,3,2,5]`,`val=[10,20,12,8,17,25]`,返回`78`.
输入:
[3,7,3,2,5]
[10,20,12,8,17,25]
输出:
78
解释:
第一个人可以完成1号作业，2号作业, 3 7<=10.
第二个人可以完成1号作业，2号作业，3号作业，4号作业和5号作业, 3 7 3 2 5<=20
第三个人可以完成1号作业，2号作业，无法完成三号作业, 3 7<=12,3 7 3>12.
第四个人可以完成1号作业，无法完成2号作业 , 3<=8,7 3>8.
第五个人可以完成1号作业，2号作业，3号作业，4号作业，无法完成5号作业,3 7 3 2<=17,3 7 3 2 5>17.
第六个人可以完成1号作业，2号作业，3号作业，4号作业和5号作业, 3 7 3 2 5<=25
3 7 3 7 3 2 5 3 7 3 3 7 3 2 3 7 3 2 5=78, 返回 78.
注意事项
1<=n<=100000
1<=m<=100000
1<=val[i]<=100000
1<=cost[i]<=1000002. 解题
- 先将做至第 i 作业的前缀和求出来
- 然后二分查找 小于等于 val 的最后一个数
class Solution {
public:
long long doingHomework(vector<int> &cost, vector<int> &val) {
// Write your code here.
long long sum = 0;
int i, j;
for(i = 0; i < cost.size(); i)
{
sum = cost[i];
cost[i] = sum;
}
sort(val.begin(),val.end());
sum = 0;
for(i = 0; i < val.size(); i)
{
if(val[i] > cost.back())
{
sum = cost.back();
continue;
}
j = bs(cost,val[i]);
if(j != -1)
sum = cost[j];
}
return sum;
}
int bs(vector<int>& cost, int v)
{
int l = 0, r = cost.size()-1, mid;
while(l <= r)
{
mid = l ((r-l)>>1);
if(cost[mid] > v)
{
r = mid -1;
}
else
{
if(mid==cost.size()-1 || cost[mid 1] > v)
return mid;
else
l = mid 1;
}
}
return -1;
}
};100% 数据通过测试 总耗时 201 ms 您的提交打败了 39.52% 的提交!
