hdu 4393 优先队列

用优先队列储存每个人的初始距离和编号，每轮求出最快的人，然后pop掉

一开始想遍历队列的，后来发现队列没办法遍历，汗-_-!

题意，给几个第一秒冲出的距离和以后速度，求每秒后最前面人的编号，求完后最前面的退出

Case #1:
1 3 2
Case #2:
4 5 3 2 1

Hint
The first case:

1st Second end
Player1  100m    (BOOM!!)
Player2  100m
Player3    3m

2nd Second end
Player2  102m    
Player3  103m    (BOOM!!)

3rd  Second end
Player2  104m    (BOOM!!)

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 const int maxn=110;
 9 int n,m,t;
10 struct node
11 {
12     int id;
13     int dis;
14     int v;
15     node(){}
16     friend bool operator<(node a,node b)
17     {
18         if(a.dis!=b.dis)    return a.dis<b.dis; //距离大的先出队
19         else return a.id>b.id;
20     }
21 };
22 priority_queue<node> q[maxn];
23 int main()
24 {
25     int i,j,k;
26     //freopen("1.in","r",stdin);
27     scanf("%d",&t);
28     node qq;
29     int s,v,ca=0;
30     while(t--)
31     {
32         ca++;
33         scanf("%d",&n);
34         for(i=1;i<=n;i++)
35         {
36             scanf("%d%d",&qq.dis,&v);
37             qq.id=i;
38             q[v].push(qq);
39         }
40         printf("Case #%d:
",ca);
41         for(i=0;i<n;i++)
42         {
43             int fast=-1,iid=0;  //最快的人距离和编号
44             for(j=1;j<=100;j++)
45             {
46                 if(!q[j].empty())
47                 {
48                     node temp=q[j].top();
49                     if(temp.dis+i*j>fast)   fast=temp.dis+i*j,iid=j;
50                     else if(temp.dis+i*j==fast&&temp.id<q[iid].top().id)iid=j;
51                 }
52             }
53             printf("%d",q[iid].top().id);
54             q[iid].pop();
55             if(i<n-1)printf(" ");
56             else printf("
");
57         }
58     }
59     return 0;
60 }

hdu 4393 优先队列

相关推荐