c++游戏有个玩法会每小时产出相应的资源,可以通过累计该资源换取一定奖励,给另一个一为整数数组res,其中res i表示从开始到i小时中累计的资源总量,给定领取奖励所需要的资源总量trget,请计算可以领取该奖励的最早时间,如果无法领奖,返回-1,
时间: 2023-05-24 12:05:42 浏览: 146
这道题目可以用双指针来解决。假设我们要领取的奖励需要的资源总量为target,我们可以用两个指针l和r分别指向数组res的开头和结尾,初始时l=0,r=0。
然后,我们可以不断移动r指针,直到res[r]-res[l]>=target。这时,我们可以算出领取奖励最早的时间为r-1,因为在这个时刻,资源总量恰好达到了target。
接下来,我们可以开始移动l指针,直到res[r]-res[l]<target,以便能够在最短时间领取奖励。同时,我们可以更新领取奖励最早的时间,因为这时资源总量又小于了target。然后再移动r指针,重复上述步骤,直到r指针到达数组末尾。
如果在移动指针的过程中出现了res[r]-res[l]<0的情况,说明无法领取该奖励,返回-1即可。
代码实现如下:
```
int earliestTime(int target, vector<int>& res) {
int l = 0, r = 0;
int earliest = INT_MAX;
while (r < res.size()) {
if (res[r] - res[l] >= target) {
earliest = min(earliest, r - 1);
while (res[r] - res[l] >= target) {
l++;
}
}
r++;
}
return (earliest == INT_MAX) ? -1 : earliest;
}
```
阅读全文