hdu 4393(优先队列）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4393

思路：考虑Si最大只有100，所以我们可以建立优先队列数组s[1..100]，对于每个优先队列，按第一关键字Fi第二关键字ID排序，每次取出所有的优先队列里最大值，然后直接计算（Time-1）*Si + Fi 找最大的way，将对应的优先队列pop并输出对应ID即可。

View Code

 1 #include<iostream>
 2 #include<queue>
 3 const int N=110;
 4 using namespace std;
 5 
 6 struct Point{
 7     int dis,id;
 8     bool operator < (const Point &p) const {
 9         if(dis!=p.dis)
10             return dis<p.dis;
11         return id>p.id;
12     }    
13 };
14 priority_queue<Point>Q[N];
15 
16 int main(){
17     int _case,t=1;
18     scanf("%d",&_case);
19     while(_case--){
20         int n,f,s;
21         scanf("%d",&n);
22         for(int i=1;i<=n;i++){
23             Point p;
24             scanf("%d%d",&f,&s);
25             p.dis=f;
26             p.id=i;
27             Q[s].push(p);
28         }
29         printf("Case #%d:\n",t++);
30         for(int i=1;i<=n;i++){
31             int max=-1,id=100000,ans;
32             for(int j=1;j<=N;j++){
33                 if(!Q[j].empty()){
34                     Point p=Q[j].top();
35                     if((i-1)*j+p.dis>max||(i-1)*j+p.dis==max&&p.id<id){
36                         max=(i-1)*j+p.dis;
37                         id=p.id;
38                         ans=j;
39                     }
40                 }
41             }
42             int tmp=Q[ans].top().id;
43             if(i==n){
44                 printf("%d\n",tmp);
45             }else 
46                 printf("%d ",tmp);
47             Q[ans].pop();
48         }
49     }
50     return 0;
51 }