http://acm.hdu.edu.cn/showproblem.php?pid=4393
题意：
n 个人赛跑，每个人有两个参数 第一秒能走的距离 f 和 第二秒 及以后 的 速度 ，求 每一秒的 冠军 （若 距离值相同 输出序号 小的）
题解：
直接暴力查找每秒最大值的n^2的做法会超时。
法一
考虑Fi最大只有500，所以501s之后只有 speed 对排名有影响（此时如果F也相同，则按ID顺序），排序即可。前501s暴力查找，然后直接按照排序结果输出。
法二
当 way 和 speed 呈二维不递增序列时，排名不会发生变化。排序后暴力查找到way和speed满足这个条件即可。
法三
考 虑Si最大只有100，所以我们可以建立优先队列数组s[1..100]，对于每个优先队列，按第一关键字Fi第二关键字ID排序，每次取出所有的优先队 列里最大值，然后直接 计算（Time-1）*Si + Fi 找最大的way，将对应的优先队列pop并输出对应ID即可。
法一
考虑Fi最大只有500，所以501s之后只有 speed 对排名有影响（此时如果F也相同，则按ID顺序），排序即可。前501s暴力查找，然后直接按照排序结果输出。
法二
当 way 和 speed 呈二维不递增序列时，排名不会发生变化。排序后暴力查找到way和speed满足这个条件即可。
法三
考 虑Si最大只有100，所以我们可以建立优先队列数组s[1..100]，对于每个优先队列，按第一关键字Fi第二关键字ID排序，每次取出所有的优先队 列里最大值，然后直接 计算（Time-1）*Si + Fi 找最大的way，将对应的优先队列pop并输出对应ID即可。
第一种解法：
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 60100
15 #define eps 1e-6
16 #define inf 9999999
17
18 using namespace std;
19 struct node
20 {
21 int f;
22 int s;
23 int id;
24
25 }p[maxn] ;
26 int vis[maxn];
27 int cmp(const node a,const node b)// 注意 排序 这
28 {
29 if( a.s != b.s) return a.s > b.s;
30 else
31 if(a.f != b.f) return a.f > b.f ;
32 else
33 return a.id < b.id;
34 }
35 int main()
36 {
37 int t,i,j,n,k,cnt;
38 int cas = 0 ;
39 //freopen("data.in","r",stdin);
40 scanf("%d",&t);
41 while(t--)
42 {
43 memset(vis,0,sizeof(vis));
44 int mx = -1;
45 scanf("%d",&n);
46 for(i = 1;i <=n;i++ )
47 {
48 scanf("%d%d",&p[i].f,&p[i].s);
49 p[i].id = i;
50 if(mx < p[i].f)
51 {
52 mx = p[i].f ;
53
54 k = i;
55
56 }
57 }
58
59 printf("Case #%d:\n",++cas);
60 printf("%d",k);
61 vis[k] = 1 ;
62
63
64 if(n > 510)cnt = 510;
65 else cnt = n;
66 for(i = 1;i <= cnt - 1;i++)
67 {
68 mx = -1;
69 for(j = 1;j <= n;j++)
70 {
71 if(!vis[j])
72 {
73 p[j].f +=p[j].s;
74 if(mx < p[j].f)
75 {
76 k = j;
77 mx = p[j].f;
78 }
79 }
80 }
81 printf(" %d",k);
82 vis[k] = 1;
83 }
84 if(cnt < n)
85 {
86 sort(p + 1,p+1+n,cmp);
87 for(i = 1; i <= n;i++)
88 {
89 if(!vis[p[i].id])
90 {
91 printf(" %d",p[i].id);
92 vis[p[i].id] = 1;
93 }
94 }
95 }
96 printf("\n");
97
98 }
99 return 0;
100 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 60100
15 #define eps 1e-6
16 #define inf 9999999
17
18 using namespace std;
19 struct node
20 {
21 int f;
22 int s;
23 int id;
24
25 }p[maxn] ;
26 int vis[maxn];
27 int cmp(const node a,const node b)// 注意 排序 这
28 {
29 if( a.s != b.s) return a.s > b.s;
30 else
31 if(a.f != b.f) return a.f > b.f ;
32 else
33 return a.id < b.id;
34 }
35 int main()
36 {
37 int t,i,j,n,k,cnt;
38 int cas = 0 ;
39 //freopen("data.in","r",stdin);
40 scanf("%d",&t);
41 while(t--)
42 {
43 memset(vis,0,sizeof(vis));
44 int mx = -1;
45 scanf("%d",&n);
46 for(i = 1;i <=n;i++ )
47 {
48 scanf("%d%d",&p[i].f,&p[i].s);
49 p[i].id = i;
50 if(mx < p[i].f)
51 {
52 mx = p[i].f ;
53
54 k = i;
55
56 }
57 }
58
59 printf("Case #%d:\n",++cas);
60 printf("%d",k);
61 vis[k] = 1 ;
62
63
64 if(n > 510)cnt = 510;
65 else cnt = n;
66 for(i = 1;i <= cnt - 1;i++)
67 {
68 mx = -1;
69 for(j = 1;j <= n;j++)
70 {
71 if(!vis[j])
72 {
73 p[j].f +=p[j].s;
74 if(mx < p[j].f)
75 {
76 k = j;
77 mx = p[j].f;
78 }
79 }
80 }
81 printf(" %d",k);
82 vis[k] = 1;
83 }
84 if(cnt < n)
85 {
86 sort(p + 1,p+1+n,cmp);
87 for(i = 1; i <= n;i++)
88 {
89 if(!vis[p[i].id])
90 {
91 printf(" %d",p[i].id);
92 vis[p[i].id] = 1;
93 }
94 }
95 }
96 printf("\n");
97
98 }
99 return 0;
100 }
第三种方法：
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 110
15 #define eps 1e-6
16 #define inf 9999999
17
18 using namespace std;
19 struct node
20 {
21 int f;
22
23 int id;
24 node(int x,int y):f(x),id(y){}
25 friend bool operator < (const node & a,const node &b)
26 {
27 if(a.f!=b.f) return a.f < b.f;
28 else return a.id > b.id ;
29 }
30 };
31
32 int main()
33 {
34 int t,i,j,n,k,cnt,d,f,s;
35 int cas = 0 ;
36 priority_queue<node>que[maxn];
37 //freopen("data.in","r",stdin);
38 scanf("%d",&t);
39 while(t--)
40 {
41
42 int mx = -1;
43
44 for(i = 0; i <maxn;i++)
45 {
46 while(!que[i].empty())que[i].pop();
47 }
48 scanf("%d",&n);
49 for(i = 1;i <=n;i++ )
50 {
51 scanf("%d%d",&f,&s);
52 que[s].push(node(f,i));
53
54 }
55
56 printf("Case #%d:\n",++cas);
57
58 for(i = 1;i <=n;i++)
59 {
60
61
62 int mx = -1;
63 d = inf;
64 for(j = 1;j <= 100;j++)
65 {
66 if(!que[j].empty())
67 { node a = que[j].top();
68
69
70 int tmp = a.f + (i - 1) *j;
71 if(tmp > mx)
72 {
73 mx = tmp;
74
75
76 k = j;
77 d = a.id;
78
79
80 }
81 if(tmp == mx)
82 {
83 if(a.id < d)
84 {
85 d = a.id;
86 k = j;
87 }
88 }
89
90 }
91 }
92 if(i == 1)
93 printf("%d",d);
94 else printf(" %d",d);
95 if(!que[k].empty())que[k].pop();
96 }
97
98 puts("");
99
100
101 }
102 return 0;
103 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 110
15 #define eps 1e-6
16 #define inf 9999999
17
18 using namespace std;
19 struct node
20 {
21 int f;
22
23 int id;
24 node(int x,int y):f(x),id(y){}
25 friend bool operator < (const node & a,const node &b)
26 {
27 if(a.f!=b.f) return a.f < b.f;
28 else return a.id > b.id ;
29 }
30 };
31
32 int main()
33 {
34 int t,i,j,n,k,cnt,d,f,s;
35 int cas = 0 ;
36 priority_queue<node>que[maxn];
37 //freopen("data.in","r",stdin);
38 scanf("%d",&t);
39 while(t--)
40 {
41
42 int mx = -1;
43
44 for(i = 0; i <maxn;i++)
45 {
46 while(!que[i].empty())que[i].pop();
47 }
48 scanf("%d",&n);
49 for(i = 1;i <=n;i++ )
50 {
51 scanf("%d%d",&f,&s);
52 que[s].push(node(f,i));
53
54 }
55
56 printf("Case #%d:\n",++cas);
57
58 for(i = 1;i <=n;i++)
59 {
60
61
62 int mx = -1;
63 d = inf;
64 for(j = 1;j <= 100;j++)
65 {
66 if(!que[j].empty())
67 { node a = que[j].top();
68
69
70 int tmp = a.f + (i - 1) *j;
71 if(tmp > mx)
72 {
73 mx = tmp;
74
75
76 k = j;
77 d = a.id;
78
79
80 }
81 if(tmp == mx)
82 {
83 if(a.id < d)
84 {
85 d = a.id;
86 k = j;
87 }
88 }
89
90 }
91 }
92 if(i == 1)
93 printf("%d",d);
94 else printf(" %d",d);
95 if(!que[k].empty())que[k].pop();
96 }
97
98 puts("");
99
100
101 }
102 return 0;
103 }