Throw nails
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1729 Accepted Submission(s): 538
Problem Description
The
annual school bicycle contest started. ZL is a student in this school.
He is so boring because he can't ride a bike!! So he decided to
interfere with the contest. He has got the players' information by
previous contest video. A player can run F meters the first second,
and then can run S meters every second.
Each player has a single
straight runway. And ZL will throw a nail every second end to the
farthest player's runway. After the "BOOM", this player will be
eliminated. If more then one players are NO.1, he always choose the
player who has the smallest ID.
annual school bicycle contest started. ZL is a student in this school.
He is so boring because he can't ride a bike!! So he decided to
interfere with the contest. He has got the players' information by
previous contest video. A player can run F meters the first second,
and then can run S meters every second.
Each player has a single
straight runway. And ZL will throw a nail every second end to the
farthest player's runway. After the "BOOM", this player will be
eliminated. If more then one players are NO.1, he always choose the
player who has the smallest ID.
Input
In the first line there is an integer T (T <= 20), indicates the number of test cases.
In each case, the first line contains one integer n (1 <= n <= 50000), which is the number of the players.
Then
n lines follow, each contains two integers Fi(0 <= Fi <= 500), Si
(0 < Si <= 100) of the ith player. Fi is the way can be run in
first second and Si is the speed after one second .i is the player's ID
start from 1.
In each case, the first line contains one integer n (1 <= n <= 50000), which is the number of the players.
Then
n lines follow, each contains two integers Fi(0 <= Fi <= 500), Si
(0 < Si <= 100) of the ith player. Fi is the way can be run in
first second and Si is the speed after one second .i is the player's ID
start from 1.
Hint
Huge input, scanf is recommended.
Huge output, printf is recommended.
Output
For each case, the output in the first line is "Case #c:".
c is the case number start from 1.
The
second line output n number, separated by a space. The ith number is
the player's ID who will be eliminated in ith second end.
c is the case number start from 1.
The
second line output n number, separated by a space. The ith number is
the player's ID who will be eliminated in ith second end.
Sample Input
2
3
100 1
100 2
3 100
5
1 1
2 2
3 3
4 1
3 4
Sample Output
Case #1:
1 3 2
Case #2:
4 5 3 2 1
Hint
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!!)
Source
解析：直接暴力搜索会超时，我们可以对数据进行预处理，提高效率。考虑到0 < Si <= 100，我们可以构造一个按Si分类的优先队列数组。每个优先队列的数据按Fi进行一级排序， 按ID进行二级排序。这样处理之后，每一秒应该出局的运动员必然在所有优先队列的队首元素中产生。我们可以枚举时间，对这个优先队列数组进行遍历，即每一秒在最多100个运动员中进行选择，找到该秒下应该出局的运动员，不断输出即可。
#include <cstdio>
#include <queue>
using namespace std; struct node{
int f,id;
bool operator<(const node& tmp)const
{
if(f != tmp.f) return f<tmp.f;
return id>tmp.id;
}
}; priority_queue<node> q[]; int main()
{
int t,n,cn = ;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i = ; i <= n; ++i){
node tmp;
int Si;
scanf("%d%d",&tmp.f,&Si);
tmp.id = i;
q[Si].push(tmp);
}
printf("Case #%d:\n",++cn);
for(int i = ; i <= n; ++i){
int res;
int maxdis = -;
int minid = 0x7fffffff;
for(int j = ; j <= ; ++j){
if(!q[j].empty()){
int dis = q[j].top().f+(i-)*j;
if(dis>maxdis || (dis == maxdis && q[j].top().id<minid)){
maxdis = dis;
minid = q[j].top().id;
res = j;
}
}
}
if(i != n)
printf("%d ",q[res].top().id);
else
printf("%d\n",q[res].top().id);
q[res].pop();
}
}
return ;
}