CF1266E Spaceship Solitaire 题解 思维
CF1266E Spaceship Solitaire
传送门
Bob is playing a game of Spaceship Solitaire. The goal of this game is to build a spaceship. In order to do this, he first needs to accumulate enough resources for the construction. There are n n n types of resources, numbered 1 1 1 through n n n. Bob needs at least a i a_i ai pieces of the i i i-th resource to build the spaceship. The number a i a_i ai is called the goal for resource i i i.
Each resource takes 1 1 1 turn to produce and in each turn only one resource can be produced. However, there are certain milestones that speed up production. Every milestone is a triple ( s j , t j , u j ) (s_j, t_j, u_j) (sj,tj,uj), meaning that as soon as Bob has t j t_j tj units of the resource s j s_j sj, he receives one unit of the resource u j u_j uj for free, without him needing to spend a turn. It is possible that getting this free resource allows Bob to claim reward for another milestone. This way, he can obtain a large number of resources in a single turn.
The game is constructed in such a way that there are never two milestones that have the same s j s_j sj and t j t_j tj, that is, the award for reaching t j t_j tj units of resource s j s_j sj is at most one additional resource.
A bonus is never awarded for 0 0 0 of any resource, neither for reaching the goal a i a_i ai nor for going past the goal — formally, for every milestone 0 < t j < a s j 0<t_j<a_{s_j} 0<tj<asj.
A bonus for reaching certain amount of a resource can be the resource itself, that is, s j = u j s_j = u_j sj=uj.
Initially there are no milestones. You are to process q q q updates, each of which adds, removes or modifies a milestone. After every update, output the minimum number of turns needed to finish the game, that is, to accumulate at least a i a_i ai of i i i-th resource for each i ∈ [ 1 , n ] i \in [1, n] i∈[1,n].
Input
The first line contains a single integer n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \leq n \leq 2 \cdot 10^5 1≤n≤2⋅105) — the number of types of resources.
The second line contains n n n space separated integers a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an ( 1 ≤ a i ≤ 1 0 9 1 \leq a_i \leq 10^9 1≤ai≤109), the i i i-th of which is the goal for the i i i-th resource.
The third line contains a single integer q q q ( 1 ≤ q ≤ 1 0 5 1 \leq q \leq 10^5 1≤q≤105) — the number of updates to the game milestones.
Then q q q lines follow, the j j j-th of which contains three space separated integers s j s_j sj, t j t_j tj, u j u_j uj ( 1 ≤ s j ≤ n 1 \leq s_j \leq n 1≤sj≤n, 1 ≤ t j < a s j 1 \leq t_j<a_{s_j} 1≤tj<asj, 0 ≤ u j ≤ n 0 \leq u_j \leq n 0≤uj≤n). For each triple, perform the following actions:
- First, if there is already a milestone for obtaining t j t_j tj units of resource s j s_j sj, it is removed.
- If u j = 0 u_j = 0 uj=0, no new milestone is added.
- If u j ≠ 0 u_j \neq 0 uj=0, add the following milestone: “For reaching t j t_j tj units of resource s j s_j sj, gain one free piece of u j u_j uj.”
- Output the minimum number of turns needed to win the game.
Output
Output q q q lines, each consisting of a single integer, the i i i-th represents the answer after the i i i-th update.
Example
Input
2
2 3
5
2 1 1
2 2 1
1 1 1
2 1 2
2 2 0
Output
4
3
3
2
3
Note
After the first update, the optimal strategy is as follows. First produce 2 2 2 once, which gives a free resource 1 1 1. Then, produce 2 2 2 twice and 1 1 1 once, for a total of four turns.
After the second update, the optimal strategy is to produce 2 2 2 three times — the first two times a single unit of resource 1 1 1 is also granted.
After the third update, the game is won as follows.
- First produce 2 2 2 once. This gives a free unit of 1 1 1. This gives additional bonus of resource 1 1 1. After the first turn, the number of resources is thus [ 2 , 1 ] [2, 1] [2,1].
- Next, produce resource 2 2 2 again, which gives another unit of 1 1 1.
- After this, produce one more unit of 2 2 2.
The final count of resources is [ 3 , 3 ] [3, 3] [3,3], and three turns are needed to reach this situation. Notice that we have more of resource 1 1 1 than its goal, which is of no use.
题目的翻译(?)
鲍勃正在玩飞船接龙游戏。这个游戏的目标是建造一艘飞船。为此,他首先需要为建造飞船积累足够的资源。资源有 n n n 种,编号为 1 1 1 到 n n n 。鲍勃需要至少 a i a_i ai 块 i i i /th资源来建造飞船。数字 a i a_i ai 被称为资源 i i i 的目标。
每种资源的生产需要 1 1 1 个回合,每个回合只能生产一种资源。然而,某些里程碑会加快生产速度。每个里程碑都是三元组 ( s j , t j , u j ) (s_j, t_j, u_j) (sj,tj,uj) ,这意味着只要鲍勃拥有 t j t_j tj 个单位的资源 s j s_j sj ,他就能免费获得一个单位的资源 u j u_j uj ,而无需花费一回合的时间。获得这些免费资源后,鲍勃就有可能为另一个里程碑申请奖励。这样,他就可以在一个回合内获得大量资源。
游戏的构造是这样的:永远不会有两个里程碑具有相同的 s j s_j sj 和 t j t_j tj 和 t j t_j tj ,也就是说,达到 t j t_j tj 个单位的资源 s j s_j sj 的奖励最多是一个额外的资源。
达到目标 a i a_i ai 或超过目标–从形式上讲,每个里程碑 0 < t j < a s j 0<t_j<a_{s_j} 0<tj<asj 都不会获得任何资源 0 0 0 的奖励。
达到一定资源量的奖励可以是资源本身,即 s j = u j s_j = u_j sj=uj 。
最初没有里程碑。您需要处理 q q q 次更新,每次更新都会增加、删除或修改一个里程碑。在每次更新之后,输出完成游戏所需的最少回合数,也就是为每个 i ∈ [ 1 , n ] i \in [1, n] i∈[1,n] 积累至少 a i a_i ai 个 i i i (th)资源。
输入格式
第一行有一个整数 n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) (1 \leq n \leq 2 \cdot 10^5) (1≤n≤2⋅105),表示资源的种类数。
第二行共有 n n n个以空格分隔的整数 a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 1 0 9 ) a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^9) a1,a2,…,an(1≤ai≤109), a i a_i ai表示需要收集第 i i i种资源的个数。
第三行有一个整数 q ( 1 ≤ q ≤ 1 0 5 ) q(1 \leq q \leq 10^5) q(1≤q≤105),表示更新的个数
接下来有 q q q行,第 j j j行有三个以空格分隔的整数 s j , t j , u j s_j,t_j,u_j sj,tj,uj ( 1 ≤ s j ≤ n , 1 ≤ t j < a s j , 0 ≤ u j ≤ n ) (1 \leq s_j \leq n,1 \leq t_j < a_{s_j},0 \leq u_j \leq n) (1≤sj≤n,1≤tj<asj,0≤uj≤n)对于每个三元组,执行以下操作:
-
首先,如果已经存在一个当积累了 t j t_j tj个 s j s_j sj种资源时给予奖励的成就,则将其删除
-
如果 u j = 0 u_j = 0 uj=0,则不执行操作
-
如果 u j ≠ 0 u_j \neq 0 uj=0,则添加如下成就:“当积累了 t j t_j tj个 s j s_j sj种资源时,赠送一个免费的 u j u_j uj种资源”
-
输出完成游戏所需的最少回合数
输出格式
输出共 q q q行,每行一个整数,表示第 i i i次修改之后的答案。
注明
以上来自 C o d e F o r c e s ,翻译: D e e p L (题目描述)、 L u o g u (输入、输出格式)。 以上来自CodeForces,翻译:DeepL(题目描述)、Luogu(输入、输出格式)。 以上来自CodeForces,翻译:DeepL(题目描述)、Luogu(输入、输出格式)。
?洛谷!!!为什么!?因为DeepL大哥好像春节放假,翻译了一半然后崩了。
解题思路
刚开始时,需要造的资源数就是所有资源之和,当一个新的里程碑加入之后,需要造的资源数( x x x)只有三种变化: x − 1 , x , x + 1 x-1,x,x+1 x−1,x,x+1,即:
- 当奖励的资源是我们需要的,那就可以少造一个;
- 当奖励的资源是多余的,那就不变;
- 当奖励的资源使我们还需要再造一个资源,即之前送的资源现在不送了,就得多造一个。
那么加入的里程碑可以分为两块来考虑,如果我们需要,可以少造一个,如果不需要,那就要多造或者不造,通过 m a p map map 来记录某条里程碑之前是否出现过,然后我们再用 c n t cnt cnt 数组记录该物品我们有了多少,就可以算最后的答案了。
AC Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int Maxn = 2e5 + 5;
int n, a[Maxn], q;
map<int, map<int, int>> mp;
int Count_Member[Maxn];
int Answer;
inline void Init();
inline void Solve();
inline void Work() {
Init();
cin >> q;
while (q--)Solve();
}
signed main() {
FAST_IO, Work();
return 0;
}
inline void Init() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i], Answer += a[i];
}
inline void Solve() {
int s, t, u;
cin >> s >> t >> u;
if (mp[s][t]) {
Count_Member[mp[s][t]]--;
if (Count_Member[mp[s][t]] < a[mp[s][t]]) Answer += 1;
mp[s][t] = u, Count_Member[u] += 1;
if (u != 0 && Count_Member[u] <= a[u]) Answer -= 1;
} else {
mp[s][t] = u, Count_Member[u] += 1;
if (Count_Member[u] <= a[u]) Answer -= 1;
}
cout << Answer << endl;
}
还有问题?评论啊。
原文地址:https://blog.csdn.net/BestMonkey/article/details/136148321
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!