【算法分析】 最优策略：每一次贪心地选当前单位重量价值最大的金属装入口袋。 【参考代码】 【时间复杂度】 O(kslog⁡2s)O(ks\log_{2}s)O(kslog2 s) 【预计得分】 100pts100pts100pts

#include<bits/stdc++.h> using namespace std; const int N=100001; struct stu{ double w,v,wv; }a[N]; bool cmp(stu aa,stu bb) { return aa.wv>bb.wv; } int main() { int k; cin>>k; while(k--) { int n,m; cin>>m>>n; for(int i=1;i<=n;i++) { cin>>a[i].w>>a[i].v; a[i].wv=a[i].v/a[i].w; } sort(a+1,a+1+n,cmp); double sum=0; for(int i=1;i<=n;++i) { if(m>=a[i].w) sum+=a[i].v; }

#include<iostream> #include<algorithm> //倒库 #include<iomanip> using namespace std; const int N=1e5+5; int t; //表次数的变量 struct Node{ //结构体 int m,v; //m表质量，v表价值 double s; //s是他俩的比值，为sort准备的 }a[N]; bool cmp(Node a,Node b){ //比较函数 return a.s>b.s; } int main(){ cin>>t; //输入次数 while(t--){ //整体循环 int w,n; //定义w用于袋子容量，n作为金属数量 double sum=0; //sum是最后的ans cin>>w>>n; for(int i=1;i<=n;i++){ cin>>a[i].m>>a[i].v; a[i].s=a[i].v1.0/a[i].m;//输入每个金属的质量和价值的同时计算单个的价值 } sort(a+1,a+n+1,cmp);//根据单价排序 for(int i=1;i<=n;i++){ //根据排序后的结果计算ans if(w==0) break; //退出 if(w<a[i].m){ //如果w不能容纳 sum+=wa[i].s; //由于金属可以随意切割，将w剩下的容量装满 w=0; //清空容量（退出循环） }else{ //如果w还够容纳当前金属的全部 sum+=a[i].v; //直接加上价值 w-=a[i].m; //w容量自动减少 } } cout<<fixed<<setprecision(2)<<sum<<endl; //保留两位小数的输出 } return 0; }

先建一个列表，存储价值/数量，排好序（连着另外两个一起排好），然后一直遍历，直到当前金属没法放下，不要去存另外的金属，把当前金属切割带走，break掉