一直都先挑单价大的卖，直到达到最大需求量。这可能是最简单的贪心算法了吧。
还有一个测试点没通过，不知道有什么问题，先不纠结了。。。
sort排序：sort 函数在头?件 #include <algorithm> ??，主要是对?个数组进?排序（ int arr[] 数组或者 vector 数组都?）， vector 是容器，要? v.begin() 和 v.end() 表示头尾；? int arr[] ? arr 表示数组的?地址， arr+n 表示尾部。sort 默认是从?到?排列的，也可以指定第三个参数 cmp 函数，然后??定义?个 cmp 函数指定排序规则。sort 函数的 cmp 必须按照规定来写，即必须只是 > 或者 < ，?如： return a > b; 或者 return a < b; ?不能是 <= 或者 >=。
cmp 最好?的还是在结构体中，尤其是很多排序的题?～?如?个学?结构体 stu 有学号和成绩两个变量，要求如果成绩不同就按照成绩从?到?排列，如果成绩相同就按照学号从?到?排列，那么就可以写?个 cmp 数组实现这个看上去有点复杂的排序过程。下面的代码示例以及上面的解释摘自柳婼大佬。
1 #include <iostream> 2 using namespace std; 3 struct stu { // 定义?个结构体stu，number表示学号，score表示分数 4 int number; 5 int score; 6 } 7 bool cmp(stu a, stu b) { // cmp函数，返回值是bool，传?的参数类型应该是结构体stu类型 8 if (a.score != b.score) // 如果学?分数不同，就按照分数从?到?排列 9 return a.score > b.score; 10 else // 如果学?分数相同，就按照学号从?到?排列 11 return a.number < b.number; 12 } 13 // 有时候这种简单的if-else语句我喜欢直接??个C语???的三?运算符表示～ 14 bool cmp(stu a, stu b) { 15 return a.score != b.score ? a.score > b.score : a.number < b.number; 16 }
#include <iostream> #include <algorithm> using namespace std; struct YB{ int sum; float ave; int pri; }yb[1000]; bool cmp(YB x,YB y){ return x.ave>y.ave; } int main(){ int n,need,sum,price; float ans=0; cin>>n>>need; for(int i=0;i<n;i++) { cin>>yb[i].sum; } for(int i=0;i<n;i++) { cin>>yb[i].pri; yb[i].ave=(float)yb[i].pri/yb[i].sum; } sort(yb,yb+n,cmp); for(int i=0;i<n;i++) { if(yb[i].sum<need) { ans+=yb[i].pri; need-=yb[i].sum; }else{ ans+=yb[i].ave*need; break; } } printf("%.2f",ans); return 0; }
下面这是最开始的代码，测试点两个没通过 不知道为嘛
#include <iostream> using namespace std; struct YB{ int sum; float ave; int pri; }yb[1005]; int main(){ int n,need,sum,price; float ans=0; cin>>n>>need; for(int i=0;i<n;i++) { cin>>yb[i].sum; } for(int i=0;i<n;i++) { cin>>yb[i].pri; yb[i].ave=(float)yb[i].pri/yb[i].sum; } while(need!=0) { float max=yb[0].ave; int maxn=0; for(int i=0;i<n;i++) { if(yb[i].ave>max) { max=yb[i].ave; maxn=i; } } if(yb[maxn].sum<need) { ans+=(float)yb[maxn].pri; need-=yb[maxn].sum; yb[maxn].ave=0.0; }else{ ans+=yb[maxn].ave*need; need=0; } } printf("%.2f",ans); return 0; }
原文：https://www.cnblogs.com/littleLittleTiger/p/10486259.html