HDU 5596 GTW likes gt（multiset）
最后更新于：2022-04-01 15:52:53
该题其实只需要利用multiset维护一下就可以了。
根据题意， 利用题目特点， 可以发现， 如果正着枚举的话， 前面的对后面的会产生影响， 但是， 如果我们倒着枚举就可以避免这个情况。
所以我们不妨先记录每个时间点释放魔法的次数， 然后倒着枚举， 这样当前这个数的能力值就是v+res （res为当前附加的魔法值， 因为后面时间增加的魔法，对于前面时间也一定增加了）。 所以， 我们不妨将每个值放进multiset， 然后二分查找对方组里是否存在比当前数大的数。 复杂度O(n*log(n))
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 50000 + 10;
const int maxv = 1000000 + 10;
int T,n,m,vis[maxv],b,time[maxn];
struct node {
int id, v;
node(int ii=0, int vv=0):id(ii), v(vv) {}
}a[maxn];
multiset<int> g1, g2;
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
g1.clear(); g2.clear();
multiset<int> :: iterator it;
memset(vis, 0, sizeof(vis));
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].id,&a[i].v);
for(int i=0;i<m;i++) {
scanf("%d",&b);
vis[b]++;
}
int res = 0, ans = 0;
for(int i=n;i>=1;i--) {
res += vis[i];
if(a[i].id == 0) {
g1.insert(a[i].v+res);
it = g2.upper_bound(a[i].v+res);
if(it != g2.end()) ++ans;
}
else {
g2.insert(a[i].v+res);
it = g1.upper_bound(a[i].v+res);
if(it != g1.end()) ++ans;
}
}
printf("%d\n",n-ans);
}
return 0;
}
~~~