这次的个人赛真是让我认清了自己的实力。。两道困难题都没做出?，虽然大家的通过率也不咋地。。
最后排名
我记录一道做出来的题吧，这道题是一道中等题，通过率如下，虽然题目不难，但由于时间限制的问题，不使用技巧很容易超出时间限制
原题
在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种，分别是文明等级（C），资源储备（R）以及人口数量（H）。在游戏开始时（第 0 天），三种属性的值均为 0。
随着游戏进程的进行，每一天玩家的三种属性都会对应增加，我们用一个二维数组 increase 来表示每天的增加情况。这个二维数组的每个元素是一个长度为 3 的一维数组，例如 [[1,2,1],[3,4,2]] 表示第一天三种属性分别增加 1,2,1 而第二天分别增加 3,4,2。
所有剧情的触发条件也用一个二维数组 requirements 表示。这个二维数组的每个元素是一个长度为 3 的一维数组，对于某个剧情的触发条件 c[i], r[i], h[i]，如果当前 C >= c[i] 且 R >= r[i] 且 H >= h[i] ，则剧情会被触发。
根据所给信息，请计算每个剧情的触发时间，并以一个数组返回。如果某个剧情不会被触发，则该剧情对应的触发时间为 -1 。
示例 1：
输入：
increase = [[2,8,4],[2,5,0],[10,9,8]]requirements = [[2,11,3],[15,10,>7],[9,17,12],[8,1,14]]输出:
[2,-1,3,-1]解释：
初始时，C = 0，R = 0，H = 0
第 1 天，C = 2，R = 8，H = 4
第 2 天，C = 4，R = 13，H = 4，此时触发剧情 0
第 3 天，C = 14，R = 22，H = 12，此时触发剧情 2
剧情 1 和 3 无法触发。
示例 2：
输入：
increase = [[0,4,5],[4,8,8],[8,6,1],[10,10,0]]requirements = [[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]输出:
[-1,4,3,3,3]
示例 3：
输入：
increase = [[1,1,1]] requirements = [[0,0,0]]输出:
[0]
限制：
1 <= increase.length <= 100001 <= requirements.length <= 1000000 <= increase[i] <= 100 <= requirements[i] <= 100000
解法
思想
见代码部分
代码
我一开始想的是用requirement里面的三元组每隔一天减去increase里面对应的三元组，然后记录答案，但是这种方法无论怎么剪枝优化都会超时，这样做的时间复杂度是O(mn)(m,n为两个数组的大小，我还省去了后面数组赋值的时间复杂度)：
class Solution {
public int[] getTriggerTime(int[][] increase, int[][] requirements) {
Integer[] ans = new Integer[requirements.length];
for(int day = 0;day<=increase.length;day++){
boolean hasRemain = false;
for(int i = 0;i<requirements.length;i++){
if(day == 0){
if(requirements[i][0]==0&&requirements[i][1]==0&&requirements[i][2]==0)
ans[i] = 0;
else continue;
}
if(ans[i]!=null) continue;
hasRemain = true;
requirements[i][0] -= increase[day-1][0];
requirements[i][1] -= increase[day-1][1];
requirements[i][2] -= increase[day-1][2];
if(requirements[i][0]<=0&&requirements[i][1]<=0&&requirements[i][2]<=0){
ans[i] = day;
}
}
if(day!=0&&!hasRemain) break;
}
int[] realAns = new int[requirements.length];
for(int i = 0;i<ans.length;i++){
if(ans[i] == null){
realAns[i] = -1;
}else{
realAns[i] = ans[i];
}
}
return realAns;
}
}
后来想到可以计算每一天的属性值，然后二分查找，这样做的时间复杂度就是O(m+nlogm)：
class Solution {
public int[] getTriggerTime(int[][] increase, int[][] requirements) {
int day = 0;
int[] ans = new int[requirements.length];
//将increase中的三元组的含义变为每一天的属性值
for(int i = 1;i<increase.length;i++){
increase[i][0] += increase[i-1][0];
increase[i][1] += increase[i-1][1];
increase[i][2] += increase[i-1][2];
}
for(int i = 0;i<requirements.length;i++){
if(requirements[i][0]==0&&requirements[i][1]==0&&requirements[i][2]==0) ans[i] = 0;
else{
int left = 0;
int right = increase.length-1;
//如果最后一天仍不满足，设为-1
if(!(increase[right][0]>=requirements[i][0]&&increase[right][1]>=requirements[i][1]&&increase[right][2]>=requirements[i][2])){
ans[i] = -1;
continue;
}
//二分查找
while(left <right){
int mid = (left+right)/2;
if(!(increase[mid][0]>=requirements[i][0]&&increase[mid][1]>=requirements[i][1]&&increase[mid][2]>=requirements[i][2])){
left = mid+1;
}else{
right = mid;
}
}
ans[i] = left+1;
}
}
return ans;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e5%8a%9b%e6%89%a3%e6%9d%af%e6%98%a5%e5%ad%a3%e4%b8%aa%e4%ba%ba%e8%b5%9b-%e5%89%a7%e6%83%85%e8%a7%a6%e5%8f%91%e6%97%b6%e9%97%b4/
