class Solution {
public:
vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
}
};
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 <= 100001 <= requirements.length <= 1000000 <= increase[i] <= 100 <= requirements[i] <= 100000原站题解
golang 解法, 执行用时: 188 ms, 内存消耗: 20.8 MB, 提交时间: 2023-09-28 15:41:22
func getTriggerTime(increase [][]int, requirements [][]int) []int {
crh := make([][]int, len(increase) + 1)
crh[0] = []int{0,0,0}
for i := 0; i < len(increase); i++ {
crh[i+1] = []int{increase[i][0] + crh[i][0], increase[i][1] + crh[i][1], increase[i][2] + crh[i][2]}
}
result := make([]int, len(requirements))
for i := 0; i < len(requirements); i++ {
l, r := 0, len(crh)
for l < r {
mid := l + (r-l)/2
if crh[mid][0] < requirements[i][0] || crh[mid][1] < requirements[i][1] || crh[mid][2] < requirements[i][2] {
l = mid + 1
}else{
r = mid
}
}
if l == len(crh) {
result[i] = -1
}else {
result[i] = l
}
}
return result
}
cpp 解法, 执行用时: 396 ms, 内存消耗: 96.2 MB, 提交时间: 2023-09-28 15:40:52
class Solution {
public:
vector<int> getTriggerTime(vector<vector<int>>& inc, vector<vector<int>>& r) {
inc.insert(begin(inc), {0,0,0});
int n = r.size(), m = inc.size();
vector<int> ans(n, -1);
for(int i = 1; i < m; ++i) for(int j = 0; j < 3; ++j) inc[i][j] += inc[i-1][j];
for(int i = 0; i < n; ++i) (
ans[i] = lower_bound(begin(inc), end(inc), r[i], [](auto& v, auto& x){
return v[0] < x[0] || v[1] < x[1] || v[2] < x[2];
}) - begin(inc)) == m ? ans[i] = -1 : EOF;
return ans;
}
};
python3 解法, 执行用时: 364 ms, 内存消耗: 74.8 MB, 提交时间: 2023-09-28 15:39:08
class Solution:
def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:
n, m = len(increase), len(requirements)
prefix = [
list(accumulate(elem, initial=0))
for elem in zip(*increase)
]
res = [-1] * m
for i, elem in enumerate(requirements):
if (idx := max(bisect_left(prefix[j], x) for j, x in enumerate(elem))) <= n:
res[i] = idx
return res
python3 解法, 执行用时: 1052 ms, 内存消耗: 74.8 MB, 提交时间: 2023-09-28 15:38:27
class Solution:
def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:
def search(arr: list, target: int) -> int:
ans = 0
left = 0
right = len(arr) - 1
if target > arr[-1]:
return right + 2
while left <= right:
mid = (left + right)//2
if arr[mid] >= target:
ans = mid
right = mid - 1
else:
left = mid + 1
return ans
a = [0]
b = [0]
c = [0]
for na, nb, nc in increase:
a.append(a[-1] + na)
b.append(b[-1] + nb)
c.append(c[-1] + nc)
ans = [-1] * len(requirements)
for i, (na, nb, nc) in enumerate(requirements):
na = search(a, na)
nb = search(b, nb)
nc = search(c, nc)
x = max(na, nb, nc)
if x <= len(increase):
ans[i] = x
return ans
java 解法, 执行用时: 39 ms, 内存消耗: 117.2 MB, 提交时间: 2023-09-28 15:37:57
class Solution {
public int[] getTriggerTime(int[][] increase, int[][] requirements) {
for(int i=1;i<increase.length;i++){for(int j=0;j<3;j++){increase[i][j]+=increase[i-1][j];}}
int ans[]=new int[requirements.length];
for(int i=0;i<requirements.length;i++){ans[i]=findTrigger(increase,requirements[i]);}
return ans;
}
public int findTrigger(int increase[][],int requirement[]){
for(int j=0;j<3;j++){if(requirement[j]>increase[increase.length-1][j]){return -1;}}
int ans=-1;
for(int j=0;j<3;j++){
if(requirement[j]==0){continue;}
int l=0,r=increase.length-1;
while(l<r){
int mid=(l+r)>>1;
if(increase[mid][j]>=requirement[j]){r=mid;}
else{l=mid+1;}
}
ans=Math.max(ans,l);
}
return ans+1;
}
}
python3 解法, 执行用时: 636 ms, 内存消耗: 75.1 MB, 提交时间: 2023-09-28 15:37:35
class Solution:
def getTriggerTime(self, increase: List[List[int]], requirements: List[List[int]]) -> List[int]:
a = [0 for i in range(3)]
#将剧情的下标记录在story中，方便映射结果
requirements = [x + [i] for i, x in enumerate(requirements)]
#将requirements按三种维度分别排序，得到 s
s = [sorted(requirements, key=lambda x: x[i]) for i in range(3)]
index = [0 for i in range(3)]
n = len(requirements)
trigger = [0 for i in range(n)]
ans = [-1 for i in range(n)]
#枚举每一天
for d, (na,nb,nc) in enumerate(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(requirements):
if na == 0 and nb == 0 and nc == 0:
ans[_] = 0
return ans