题目链接： 点我 题目大意： 给出物品的w和v，选出k个物品使得 s值最大。 题目分析： 不能直接按照v/w贪心来做，举个反例： w v 2 2 5 3 2 1 选1和3，结果是0.75，但选1和2，结果是5/7 = 0.7140 下面搬运一下《挑战程序设计》
Problem: 3111 User: ChenyangDu Memory: 1860K Time: 4360MS Language: G++ Result: Accepted #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 100000+5,INF = 0x7fffffff; int n,m; double mid; struct jew {int v,w,id;}in[maxn]; bool cmp (jew a,jew b){ double aa = (double)a.v - mid*(double)a.w; double bb = (double)b.v - mid*(double)b.w; return aa>bb; } int C(double x){ double sum = 0; for(int i=0;i<m;i++){ jew a = in[i]; sum += (double)a.v - x*(double)a.w; if(sum<0)return i; } return m; } int main(){ //freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%d%d",&in[i].v,&in[i].w); in[i].id = i+1; } double l = 0,r = INF; int T = 52; while(T--){ mid = (l+r)/2; sort(in,in+n,cmp); if(C(mid) >= m)l = mid; else r = mid; } for(int i=0;i<m;i++) printf("%d ",in[i].id); fclose(stdin); return 0; }