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

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

省流：和金银岛差不多

#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; }