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

最后排名

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

原题

在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种，分别是文明等级（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/

力扣杯春季个人赛-剧情触发时间

原题

解法

思想

代码

发表回复

力扣杯春季个人赛-剧情触发时间

原题

解法

思想

代码

相关推荐

发表回复