HDU 4393 Throw nails（貪欲にシミュレーションを加え、問題を追究する）

テーマリンク:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=115361#problem/D
最大50000人を与え、最初の速度Fと1秒後の速度Vを与え、（F<=500、V==100）毎秒で一番速い人を淘汰し、淘汰した人の順番で彼らの番号を出力します。
人数が多いので、暴力的に更新して、毎秒淘汰する人は明らかにTLEができます。Fが小さいことに気づいたら、どの二人にとっても、500キロの差があっても、そのスピードが速い人は毎秒1メートルしかないです。501秒後に超えることができます。つまり、501秒後にスピードが速い人はずっと速い地位にあります。同じスピードの人はFサイズの先に淘汰されます。同じ番号で先に淘汰すればいいです。501秒以降はこの方法で順番を並べばいいです。501秒以内であれば、暴力シミュレーションは毎秒淘汰されます。
もちろん、これはFの範囲によって考えたので、Vの範囲が小さい方法はまだできません。
ACコードは以下の通りです。
　　

 1 #include 
 2 #include 
 3 #include <set>
 4 #include <string.h>
 5 using namespace std;
 6 struct node
 7 {
 8     int id;
 9     int v;
10     int f;
11     int s;
12 }P[50000+5];
13 int tot;
14 bool cmp(node A,node B)
15 {
16     if(A.v==B.v)
17     {
18         if(A.f==B.f)
19         {
20             return A.id<B.id;
21         }
22         else return A.f>B.f;
23     }
24     else return A.v>B.v;
25 }
26 
27 int main()
28 {
29     int T;
30     scanf("%d",&T);
31     for(int kace=1;kace<=T;kace++)
32     {
33         tot=0;
34         int n;
35         scanf("%d",&n);
36         for(int i=1;i<=n;i++)
37         {
38             int f,v;
39             scanf("%d%d",&f,&v);
40             P[++tot]=(node){i,v,f,f};
41         }
42         printf("Case #%d:
",kace);
43         for(int i=1;i<=501;i++)
44         {
45             if(i>n) break;
46             int id=1;
47             int maxsum=-1;
48             for(int j=1;j<=tot;j++)
49             {
50                 if(i!=1&&P[j].s!=-1) P[j].s+=P[j].v;
51                 if(maxsum
P[j].s;}
52             }
53             if(i!=1) printf(" ");
54             printf("%d",id);
55             P[id].s=P[id].f=P[id].v=-1;
56         }
57         sort(P+1,P+1+tot,cmp);
58         for(int i=1;i<=n-501;i++)
59         {
60             printf(" %d",P[i].id);
61         }
62         puts("");
63     }
64     return 0;
65 }

 
転載先:https://www.cnblogs.com/zzyDS/p/5474026.html