HDU 4393 Throw nails （暴力加排序）

HDU 4393 Throw nails （暴力加排序）

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.

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.
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.

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

題意： n個人跑步，求每一秒跑在最前面的人。每個人的第一秒的速度為f，之後的速度都為s。

直接模擬肯定超時，可以用優先隊列來做，可是考慮第一秒的速度不大於500，那麼過了501秒之後勝負就已經分出，前501秒暴力求解，之後按照501秒時的距離排序即可。

#include
#include
#include
using namespace std;
const int MAX = 0x3f3f3f3f;
int T, n;
struct C {
    int f, s, d, p;
} a[50005];
int cmp (C x, C y) {
    if(x.d != y.d) return x.d > y.d;
    else return x.p < y.p;
}
int main()
{
    scanf("%d", &T);
    for(int ca = 1; ca <= T; ca++) {
        scanf("%d", &n);
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].f, &a[i].s);
        for(int i = 1; i <= n; i++) a[i].p = i;
        printf("Case #%d:\n", ca);
        int ans = 0, pos;
        for(int i = 1; i <= n; i++) {
            a[i].d += a[i].f;
            if( a[i].d > ans ) {
                ans = a[i].f;
                pos = i;
            }
        }
        a[pos].d = MAX;
        printf("%d", pos);
        for(int i = 2; i <= min(502, n); i++) {
            ans = 0;
            for(int j = 1; j <= n; j++) {
                if(a[j].d == MAX) continue;
                a[j].d += a[j].s;
                if( a[j].d > ans ) {
                    ans = a[j].d;
                    pos = j;
                }
            }
            a[pos].d = MAX;
            printf(" %d", pos);
        }
        sort(a+1, a+1+n, cmp);
        for(int i = 503; i <= max(n, 502); i++) 
            printf(" %d", a[i].p);
        printf("\n");
    }
    return 0;
}