此题可以通过排序来解决。考虑一个可行的但不一定是最优的操作序列，第i个之前的已经完成。如果交换i和i+1，容易想到这不会对之后产生的结果有任何影响，那么是先完成i还是先完成i+1呢？
以下是我的代码：
#include<stdio.h>
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
long test,first=1;
scanf("%ld",&test);
while(test--)
{
const long maxn=1007,INF=20000000;
long n,id[maxn],t[maxn],s[maxn];
scanf("%ld",&n);
for(long i=1;i<=n;i++)
{
scanf("%ld%ld",&t[i],&s[i]);id[i]=i;
}
// Read In
for(long i=1;i<=n;i++)
for(long j=n-1;j>=i;j--)
if(s[j]*t[j+1]<s[j+1]*t[j])
{
long tmp;
tmp=id[j];id[j]=id[j+1];id[j+1]=tmp;
tmp=t[j];t[j]=t[j+1];t[j+1]=tmp;
tmp=s[j];s[j]=s[j+1];s[j+1]=tmp;
}
if(first) first=0;
else putchar('\n');
for(long i=1,first=1;i<=n;i++)
{
if(first) first=0;
else putchar(' ');
printf("%ld",id[i]);
}
putchar('\n');
}
return 0;
}
posted on 2010-02-05 16:14
lee1r 阅读(700)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构