BestCoder Round #32_1001 以及 hdu 5182

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=570&pid=1001

 http://acm.hdu.edu.cn/showproblem.php?pid=5182

这道题也是hdu上的5182

官方题解：

对于输入的每一行一两个整数作差,按照差值从大到小排序,如果差值一样,按照后面的整数从小到大排序，如果还是一样按照ID从小到大排序。

首先注意下数据范围，大约100组数据，所有整数都在[1,100] 的范围内，即使是用冒泡法或者选择法排序也不会TLE。其次就要考虑如何将城市的标号一并排序，可以构建一个专门保存城市标号的数组，排序的时候按城市标号对应的数据进行比较，只改变城市标号的位置，数据不用排序。、

先贴一个最简单的代码。

#include<stdio.h>

int main()
{
    int i,j,n,pm[110][2],c[110],t,s[110];

    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&pm[i][0],&pm[i][1]);
            c[i]=pm[i][0]-pm[i][1];
            s[i]=i;                            //s数组记录城市的标号
        }
        for(i=0;i<n-1;i++)                     //首先按照差值排序，注意只是将城市的标号排序
        {
            for(j=0;j<n-1-i;j++)
            {
                if(c[s[j]]<c[s[j+1]])
                {
                    t=s[j];
                    s[j]=s[j+1];
                    s[j+1]=t;
                }
            }
        }
        for(i=0;i<n-1;i++)                      //按照第二次的测量值升序排序，同样将城市的标号排序
        {
            if(c[s[i]]==c[s[i+1]])
            {
                if(pm[s[i]][1]>pm[s[i+1]][1])
                {
                    t=s[i];
                    s[i]=s[i+1];
                    s[i+1]=t;
                    if(i>0)
                        i=i-2;
                }
            }
        }
        for(i=0;i<n-1;i++)                       //按照输入的顺序排序
        {
            if(c[s[i]]==c[s[i+1]])
            {
                if(pm[s[i]][1]==pm[s[i+1]][1])
                {
                    if(s[i]>s[i+1])
                    {
                        t=s[i];
                        s[i]=s[i+1];
                        s[i+1]=t;
                        if(i>0)
                            i=i-2;
                    }
                }
            }
        }
        for(i=0;i<n;i++)
        {
            if(i==0)
                printf("%d",s[i]);
            else
                printf(" %d",s[i]);
        }
        printf("
");
    }
    return 0;
}

赛后觉得时间用的太多，发现可以用一个结构体将数据保存，用sort函数排序，只要写一下cmp函数。

代码如下：

#include<stdio.h>
#include<algorithm>

using namespace std;

struct node
{
    int pm1;
    int pm2;
    int decrease;
    int number;
}city[110];

bool cmp(struct node x,struct node y)
{
    if(x.decrease!=y.decrease)
        return x.decrease>y.decrease;
    if(x.pm2!=y.pm2)
        return x.pm2<y.pm2;
    return x.number<y.number;
}

int main()
{
    int n;

    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&city[i].pm1,&city[i].pm2);
            city[i].decrease=city[i].pm1-city[i].pm2;
            city[i].number=i;
        }
        sort(city,city+n,cmp);
        for(int i=0;i<n;i++)
        {
            if(i==0)
                printf("%d",city[i].number);
            else
                printf(" %d",city[i].number);
        }
        printf("
");
    }
    return 0;
}