题目:
从前,有n只萌萌的糖糖,他们分成了两组一起玩游戏。他们会排成一排,第i只糖糖会随机得到一个能力值bi。从第i秒的时候,第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。
为了使游戏更加有趣,糖糖的爸爸,娇姐,会发功m次,第i次发功的时间为ci,则在第ci秒结束后,b1,b2,.....,bci都会增加1.
现在,娇姐想知道在第n秒后,会有多少只糖糖存活下来。
做法:
为每组开个优先队列。第个人加入时就在敌对队列中不断pop出
的人就行了。
至于题目中能力值的修改。由于是个整体修改。用一个全局变量维护就好。表示前面所有人能力的上升值。每个人的能力值就能用队列中的能力值+exa表示。注意push的时候要减去此时的exa。这部分看代码理解一下下。
代码:
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl using namespace std; typedef long long ll; const int N = 5e4 + 7; int a[N], b[N], c[N]; int main(void){ IOS; int T; cin >> T; while (T--){ int n, m; cin >> n >> m; memset(c, 0, sizeof c); for (int i = 1; i <= n; ++i){ cin >> a[i] >> b[i]; } for (int i = 1; i <= m; ++i){ int x; cin >> x; c[x]++; } priority_queue<int, vector<int>, greater<int> > q[2]; int exa = 0, die = 0; for (int i = 1; i <= n; ++i){ while (!q[a[i]^1].empty() && q[a[i]^1].top()+exa < b[i]) q[a[i]^1].pop(), die++; q[a[i]].push(b[i]-exa); exa += c[i]; } cout << n-die << endl; } return 0; }