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

题意概述

题目大意是有一个游戏，随着时间的增加我们的属性会不断提升。当属性大于某个临界点时会触发相应剧情，最后问每个剧情触发的时间。

题解

简化问题

在原问题比较复杂时，我们可以先考虑简化问题的情况。原问题中有三种不同的属性，三种属性均满足要求才会触发相应剧情。这里我们可以先考虑简化为只有一种属性。

解法 1

如果只有一种属性，显然我们只需要计算每一天的属性情况，最后对于所有的requirements 都在属性列表中进行二分查找（现在只有一种属性了)，就能知道他是在哪一天完成的了。

解法 2

还可以换一个思路，计算完每一天的属性情况后，我们将 requirements 中的单属性也同样进行排序，放入一个队列中。

接着，我们遍历每一天的属性情况，由于 requirements 也是排序过的，我们只需要看队首有多少元素满足当前触发要求，满足则触发就可以了。

原始问题

以上只是单属性的做法，原始题目中给了多达三种属性。但是实际上，每一种属性的满足是互相独立的。

简单来说，对于一个剧情要求 (C, R, H) 来说，假设 C 要求是在第 x 天满足的，R要求是在第 y 天满足的，H 要求是在第 z 天满足的。那么该剧情的满足时间为：

t = \max(x, y, z)

而每一个属性在什么时间满足，正好是我们前面提到的简化问题。至此，原始问题的解法也清晰了：

1. 根据简化问题，分别只考虑三种属性，计算各剧情三种属性的触发时间。
2. 根据上式计算各剧情的最终触发时间。

class Solution(object):
    def getTriggerTime(self, day_increase, story_requires):
        """
        :type day_increase: List[List[int]]
        :type story_requires: List[List[int]]
        :rtype: List[int]
        """
        a = [0 for i in range(3)]
        #将剧情的下标记录在story中，方便映射结果
        story_requires = [x + [i] for i, x in enumerate(story_requires)]
        #将requirements按三种维度分别排序，得到 s
        s = [sorted(story_requires, key=lambda x: x[i]) for i in range(3)]
        index = [0 for i in range(3)]

        n = len(story_requires)
        trigger = [0 for i in range(n)]
        ans = [-1 for i in range(n)]
        #枚举每一天
        for d, (na,nb,nc) in enumerate(day_increase):
            #计算当天的属性
            a[0] += na; a[1] += nb; a[2] += nc
            #遍历三种属性的排序序列，计算当前可以被触发的剧情
            for i in range(3):
                while index[i] < n and a[i] >= s[i][index[i]][i]:
                    trigger[s[i][index[i]][-1]] += 1
                    #如果某个剧情触发次数等于3次(三种属性均触发，剧情被实际触发)
                    if trigger[s[i][index[i]][-1]] == 3:
                        ans[s[i][index[i]][-1]] = d + 1
                    index[i] += 1
        #第0天单独考虑
        for i, (na, nb, nc, _) in enumerate(story_requires):
            if na == 0 and nb == 0 and nc == 0:
                ans[_] = 0
        return ans

复杂度分析

• 时间复杂度：O(n * \log(n))。对属性的排序为整体的时间复杂度瓶颈。

• 空间复杂度：O(n)。

拓展

题目本质能解的原因是各个属性的达成是互相独立的。在这个基础上，可以有许多不同的变种。例如如果要求改成触发某一个属性即能触发剧情的话，将上式中的 max 改为 min 即可。