首页 > ACM题库 > HDU-杭电 > HDU 4393-Throw nails-优先队列-[解题报告]HOJ
2015
05-24

HDU 4393-Throw nails-优先队列-[解题报告]HOJ

Throw nails

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

2
3
100 1
100 2
3 100
5
1 1
2 2
3 3
4 1
3 4

样例输出:

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!!)

题目大意:

给你n个人,他们在进行一场自行车竞速比赛,每个人在第1s时走fi米,以后每秒走si米,一个小孩在仍钉子破坏比赛,每秒他都选最靠前的那个人,如果有多个人,选编号最小的那个,问你这些人依次被破退出比赛的顺序。(1 <= n <= 50000)(0 <= Fi <= 500)(0 < Si <= 100)

题解:

下面是官方的题解,比赛时我没做出来,原因在于忘记了(0 < Si <= 100)的数据范围.

法一
考虑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即可。     

下面是用第三种方法AC的程序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
struct node
{
    int f,id;
    bool operator<(const node& b)const
    {
        return (f<b.f)||(f==b.f && id>b.id);
    }
};
priority_queue<node> s[120];
int sec,n;
int main()
{
    scanf("%d",&sec);
    for(int z=1;z<=sec;z++)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            node t;int f,d;
            scanf("%d%d",&f,&d);
            t.f=f;
            t.id=i;
            s[d].push(t);
        }

        printf("Case #%d:\n",z);
        for(int i=1;i<=n;i++)
        {
            int maxx=-1,minid=1<<28;int re;
            for(int j=1;j<=100;j++)
            if(!s[j].empty())
            {
                node t=s[j].top();
                if((i-1)*j+t.f>maxx || ((i-1)*j+t.f==maxx && t.id<minid))
                {
                    maxx=(i-1)*j+t.f;
                    re=j;
                    minid=t.id;
                }
            }
            int tem=s[re].top().id;
            if(i==n)printf("%d\n",tem);else printf("%d ",tem);
            s[re].pop();
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/hyogahyoga/article/details/7901921