此題可以通過排序來解決。考慮一個可行的但不一定是最優的操作序列，第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 閱讀(703)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構