这次的个人赛真是让我认清了自己的实力。。两道困难题都没做出?,虽然大家的通过率也不咋地。。

最后排名

我记录一道做出来的题吧,这道题是一道中等题,通过率如下,虽然题目不难,但由于时间限制的问题,不使用技巧很容易超出时间限制

原题
在战略游戏中,玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种,分别是文明等级(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 <= 10000
1 <= requirements.length <= 100000
0 <= increase[i] <= 10
0 <= 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/