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[][],c[],t,s[]; while(scanf("%d",&n)!=EOF)
{
for(i=;i<n;i++)
{
scanf("%d%d",&pm[i][],&pm[i][]);
c[i]=pm[i][]-pm[i][];
s[i]=i; //s数组记录城市的标号
}
for(i=;i<n-;i++) //首先按照差值排序，注意只是将城市的标号排序
{
for(j=;j<n--i;j++)
{
if(c[s[j]]<c[s[j+]])
{
t=s[j];
s[j]=s[j+];
s[j+]=t;
}
}
}
for(i=;i<n-;i++) //按照第二次的测量值升序排序，同样将城市的标号排序
{
if(c[s[i]]==c[s[i+]])
{
if(pm[s[i]][]>pm[s[i+]][])
{
t=s[i];
s[i]=s[i+];
s[i+]=t;
if(i>)
i=i-;
}
}
}
for(i=;i<n-;i++) //按照输入的顺序排序
{
if(c[s[i]]==c[s[i+]])
{
if(pm[s[i]][]==pm[s[i+]][])
{
if(s[i]>s[i+])
{
t=s[i];
s[i]=s[i+];
s[i+]=t;
if(i>)
i=i-;
}
}
}
}
for(i=;i<n;i++)
{
if(i==)
printf("%d",s[i]);
else
printf(" %d",s[i]);
}
printf("\n");
}
return ;
}
赛后觉得时间用的太多，发现可以用一个结构体将数据保存，用sort函数排序，只要写一下cmp函数。
代码如下：
#include<stdio.h>
#include<algorithm> using namespace std; struct node
{
int pm1;
int pm2;
int decrease;
int number;
}city[]; 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=;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=;i<n;i++)
{
if(i==)
printf("%d",city[i].number);
else
printf(" %d",city[i].number);
}
printf("\n");
}
return ;
}