力扣LCP 08.剧情触发时间
力扣LCP 08.剧情触发时间
-
前缀和 + 二分
- 对increase求前缀和 在前缀和数组上做二分 找到符合要求的最小时间
-
class Solution {public:vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {//第一维increase.size() + 1 , 第二维大小为3的数组初值为0(不加也可以 默认为0)vector<vector<int>> s(increase.size()+1,vector<int>(3/*,0*/));for(int i=0;i<increase.size();i++)for(int j=0;j<3;j++)s[i+1][j] = s[i][j] + increase[i][j];vector<int> ans;for(auto v:requirements){int l = 0 ,r = increase.size();while(l<r){int mid = l + r >> 1;if(s[mid][0]>=v[0]&&s[mid][1]>=v[1]&&s[mid][2]>=v[2]) r = mid;else l = mid+1;}if(s[l][0]>=v[0]&&s[l][1]>=v[1]&&s[l][2]>=v[2])ans.emplace_back(l);else ans.emplace_back(-1);}return ans;}};