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存活下来。$

总共

输入样例

1　　//测试数据个数
4 3　　//n个gtm,m次发功
0 3
1 2
0 3
1 1
1　　//发功时间
3
4

输出样例

 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 }

秒客网

GTW likes gt（BC 模拟 or 优先队列）

GTW likes gt

相关文章