README.md

LCP 08. 剧情触发时间

题目描述

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

解法

方法一：前缀和 + 二分查找

Python3

class Solution:
    def getTriggerTime(
        self, increase: List[List[int]], requirements: List[List[int]]
    ) -> List[int]:
        increase.insert(0, [0, 0, 0])
        m, n = len(increase), len(requirements)
        for i in range(1, m):
            for j in range(3):
                increase[i][j] += increase[i - 1][j]
        ans = [-1] * n
        for i, req in enumerate(requirements):
            left, right = 0, m
            while left < right:
                mid = (left + right) >> 1
                if all(a >= b for a, b in zip(increase[mid], req)):
                    ans[i] = mid
                    right = mid
                else:
                    left = mid + 1
        return ans

Java

class Solution {
    public int[] getTriggerTime(int[][] increase, int[][] requirements) {
        int m = increase.length, n = requirements.length;
        int[][] s = new int[m + 1][3];
        for (int j = 0; j < 3; ++j) {
            for (int i = 0; i < m; ++i) {
                s[i + 1][j] = s[i][j] + increase[i][j];
            }
        }

        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for (int i = 0; i < n; ++i) {
            int left = 0, right = m + 1;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (check(s[mid], requirements[i])) {
                    ans[i] = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
        }
        return ans;
    }

    private boolean check(int[] a, int[] b) {
        for (int i = 0; i < 3; ++i) {
            if (a[i] < b[i]) {
                return false;
            }
        }
        return true;
    }
}

...