GTW likes gt(BC 模拟 or 优先队列)

时间:2022-12-15 22:47:14

GTW likes gt

Accepts: 54
Submissions: 782
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)

从前,有nnn只萌萌的GT,他们分成了两组在一起玩游戏。他们会排列成一排,第iii只GT会随机得到一个能力值bib_ibi​​。在第iii秒的时候,第iii只GT可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的GT。
为了使游戏更加有趣,GT的首领GTW会发功m次,第i次发功的时间为ci,则在第ci​​秒结束后,b1,b2,...,bci都会增加1。
现在,GTW想知道在第nnn秒之后,会有几只GT存活下来。

总共TTT行,第iii行表示第iii组数据中,GT存活的个数。 
输入样例
1  //测试数据个数
4 3  //n个gtm,m次发功
0 3
1 2
0 3
1 1
1  //发功时间
3
4
输出样例
3

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 struct gt
 6 {
 7     int pos,d;
 8     int b;
 9 }g[50000+10];
10 int    c[50000+10];
11 int n,m;
12 int main()
13 {
14     int i,j;
15     int T;
16     freopen("in.txt","r",stdin);
17     cin>>T;
18     while(T--)
19     {
20         int co=0;
21         scanf("%d%d",&n,&m);
22         for(i=0;i<n;i++)    scanf("%d%d",&g[i].pos,&g[i].b);
23         for(i=0;i<m;i++)    scanf("%d",&c[i]);
24         sort(c,c+m);
25         for(i=0;i<n;i++)
26             g[i].d=1;
27         for(i=0;i<m;i++)
28         {
29             int t=c[i]-1;
30             for(int p=0;p<=t;p++)
31                 g[p].b++;
32         }
33         for(i=1;i<n;i++)
34         {
35             for(j=0;j<i;j++)
36             {
37                 if(g[j].d==1&&g[j].pos!=g[i].pos&&g[i].b>g[j].b)
38                 {
39                     g[j].d=0;
40                     co++;
41                 }
42             }
43         }
44         printf("%d\n",n-co);
45     }
46 }

 


应大神的的代码:
 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 #define for1to(i,n) for(int i=1;i<=n;i++)
 5 #define forto(i,n) for(int i=0;i<n;i++)
 6 #define CLR(x)    memset(x,0,sizeof(x))
 7 using namespace std;
 8 int a[51111],b[51111];
 9 int c[51111];
10 int main()
11 {
12     ios_base::sync_with_stdio(false);
13     int Total;
14     cin>>Total;
15     for1to(Case,Total)
16     {
17         priority_queue<int,vector<int>,greater<int> > pq1;
18         priority_queue<int,vector<int>,greater<int> > pq0;
19         int n,m;
20         cin>>n>>m;
21         forto(i,n)
22             cin>>a[i]>>b[i];
23         CLR(c);
24         forto(i,m)
25         {
26             int t;
27             cin>>t;
28             t--;
29             c[t]++;
30         }
31         int time=0;
32         int nres=0;
33         for(int i=0;i<n;i++)
34         {
35             b[i]-=time;
36             time+=c[i];
37             if (a[i]==0)
38             {
39                 while(!pq1.empty()&&pq1.top()<b[i])
40                 {
41                     nres++;
42                     pq1.pop();
43                 }
44                 pq0.push(b[i]);
45             }
46             else
47             {
48                 while(!pq0.empty()&&pq0.top()<b[i])
49                 {
50                     nres++;
51                     pq0.pop();
52                 }
53                 pq1.push(b[i]);
54             }
55         }
56         cout<<n-nres<<endl;
57     }
58     return 0;
59 }