lintcode1753. 写作业

女爷i 2023-07-04 15:58 17阅读 0赞

n个人，他们每个人需要独立做m份作业。  
第i份作业需要花费cost\[i\]的时间。由于每个人的空闲时间不同，第i个人有val\[i\]的时间，这代表他做作业的总时间不会超过val\[i\]。每个人都按照顺序，从1号作业开始，然后做2号，3号… 现在，你需要计算出他们最多花了多少的时间。

样例
    样例 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]<=100000

class Solution {
        
    public:
        /**
         * @param cost: the cost
         * @param val: the val
         * @return: the all cost
         */
        long long doingHomework(vector<int> &cost, vector<int> &val) {
        
            // Write your code here.
            int clen=cost.size();
            int vlen=val.size();
            vector<int>sums(clen,0);
            int sum=0;
            for (int i = 0; i < clen; i++) {
        
                /* code */
                sum+=cost[i];
                sums[i]=sum;
            }
            long long res=0;
            for (auto v : val) {
        
                /* code */
                res+=search(sums,v);
            }
            return res;
        }
        long long search(vector<int> sum,int val)
        {
        
            if(val>=sum[sum.size()-1]) return sum[sum.size()-1];
            else if(val<sum[0]) return 0;
            else
            {
        
                int left=0;
                int right=sum.size()-1;
                while(left<=right)
                {
        
                    int mid=left+(right-left)/2;
                    if(sum[mid]>val) right=mid-1;
                    else if(sum[mid]<=val&&sum[mid+1]>val) return sum[mid];
                    else if(sum[mid]<val&&sum[mid+1]<=val) left=mid+1;
                }
            }
        }
    };