【算法分析】 最优策略：每一次贪心地选当前单位重量价值最大的金币装入口袋。 【参考代码】 【时间复杂度】 O(nlog2n)O(nlog_2n)O(nlog2 n) 【预计得分】 100pts100pts100pts

由于金币可以随意分割，所以我们选性价比最高的即可。（原题面中，“小码君”实为“alibaba”）

省流：和金银岛差不多

#include <bits/stdc++.h> using namespace std; struct Gold { int weight; int value; double ratio; }; bool compare(Gold a, Gold b) { return a.ratio > b.ratio; } int main() { int N, T; cin >> N >> T; Gold golds[100]; for(int i = 0; i < N; i++) { cin >> golds[i].weight >> golds[i].value; golds[i].ratio = (double)golds[i].value / golds[i].weight; } sort(golds, golds + N, compare); double total = 0.0; for(int i = 0; i < N && T > 0; i++) { if(golds[i].weight <= T) { total += golds[i].value; T -= golds[i].weight; } else { total += golds[i].ratio * T; T = 0; } } cout << fixed << setprecision(2) << total << endl; return 0; }

#include<bits/stdc++.h> using namespace std; struct coin { int m; int v; double avg; }c[1050]; bool cmp(coin c1,coin c2) { return c1.avg>c2.avg; } int main() { int n,t;cin>>n>>t; for(int i = 1;i<=n;i++) { cin>>c[i].m>>c[i].v; c[i].avg = c[i].v1.0/c[i].m; } sort(c+1,c+1+n,cmp); double sum=0; for(int i=1;i<=n;i++) { if(c[i].m<=t) { sum+=c[i].v; t -= c[i].m; } else { sum+=tc[i].avg; t=0; break; } } printf("%.2f",sum); return 0; }

#include<bits/stdc++.h> using namespace std; struct n{ int w,v; }a[110]; bool cmp(n x,n y){ return x.vy.w>x.wy.v; } int main(){ int n,m; cin>>n>>m; double ans=0; for(int i=0;i<n;i++) cin>>a[i].w>>a[i].v; sort(a,a+n,cmp); for(int i=0;i<n;i++) if(a[i].w<=m) ans+=a[i].v,m-=a[i].w; else{ans+=a[i].vm1.0/(double)a[i].w;break;} printf("%.2lf",ans); return 0; }