好像格式出了点问题,但是问题不大,这题会做,不过wa了好多,果然好久不做多组输入的题就是容易wa
解题思路:
- 首先我们利用差分的思想处理b数组(也就是发功),这里存储和差分一样,不过我们处理的时候是从后往前,因为他每次都是从1开始
- 然后我们剩下的就是求出a[i], 循环从后向前在处理差分数组的时候就可以求出a[i]的值
- 然后我们对 id1 与 id2 赋初值 - 1, 然后从后向前循环判断就OK, 这里需要的是看好数据范围记得开long long
- 因为多组输入,b 数组忘记初始化wa了好几发
代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 50010; struct node { int id; long long w; }a[N]; int b[N]; int main(){ int t; scanf("%d",&t); while(t--){ memset(b,0,sizeof b); int res = 0; int n, k; scanf("%d%d",&n,&k); for (int i = 1; i <= n; i ++){ scanf("%d%lld",&a[i].id,&a[i].w); } for (int i = 0 ; i < k; i ++){ int x; scanf("%d",&x); b[x] ++; } for (int i = n ; i >= 1; i --){ b[i] += b[i + 1]; a[i].w = a[i].w + b[i]; } long long id1 = -1; long long id2 = -1; for (int i = n ; i >= 1; i --){ if (a[i].id == 1){ id1 = max(id1,a[i].w); if (id2 > a[i].w){ res ++; } } else{ id2 = max(id2,a[i].w); if (id1 > a[i].w){ res++; } } } printf("%d\n",n - res); } }