L2-003 月饼

题目：

思路：

    一直都先挑单价大的卖，直到达到最大需求量。这可能是最简单的贪心算法了吧。

    还有一个测试点没通过，不知道有什么问题，先不纠结了。。。

知识点for me:

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