原题: http://acm.nyist.net/JudgeOnline/problem.php?pid=248
//nyoj 248 //贪心:关键在于把路程的费用也加入到商品的单价中来，然后每次买单价最低的商品 就可以了。 #include<iostream> #include<cstdio> #include<string> #include<algorithm> using namespace std; struct W { int wi; int vi; }w[101]; int cmp(const void *aa,const void *bb) { W a=*(W *)aa; W b=*(W *)bb; return a.vi>b.vi;//找单位价值最小的 } int main() { int t; while(~scanf("%d",&t)) { while(t--) { int need,end,n; scanf("%d %d %d",&need,&end,&n); for(int i=0;i<n;i++) { int pos; scanf("%d %d %d",&pos,&w[i].wi,&w[i].vi); w[i].vi+=end-pos; } qsort(w,n,sizeof(w[0]),cmp); int sum=0; for(int i=0;i<n;i++) { if(need>=w[i].wi) { sum+=w[i].wi*w[i].vi; need-=w[i].wi; }else{ sum+=w[i].vi*need; break; } } printf("%d\n",sum); } } return 0; }