题意：一张CD上有n首频率为f[i],长度为了l[i]的曲子,因为CD不能随机播放曲子，想播放第i首时，必须依次播放前i-1,
b[i]=f[i]*(a[1]+...+a[i]),sum=b[1]+..+b[n],求使sum最小的歌曲排列方式。
思路：那么b[i]+b[i+1] = (f[i] + f[i+1]) * (a[1]+ ... +a[i-1]) + f[i+1]*a[i+1] + f[i+1]*a[i] +
f[i]*a[i], 如果将换两个的位置的话，差别在与f[i]*a[i+1] 与 f[i+1]*a[i] 的大小，那么我们只要排序的时候将较小的放前面就行了
#include#include #include #include using namespace std; const int MAXN = 100010; struct node{ int id; long long l; double f; }arr[MAXN]; int n; bool cmp(node a,node b){ return a.l*b.f < b.l*a.f; } int main(){ while (scanf("%d",&n) != EOF){ for (int i = 1; i <= n; i++) scanf("%d%lld%lf",&arr[i].id,&arr[i].l,&arr[i].f); sort(arr+1,arr+1+n,cmp); int t; scanf("%d",&t); printf("%d\n",arr[t].id); } return 0; }