PAT甲级1070.

目录

A1070

题目

样例

输入:

3 200
180 150 100
7.5 7.2 4.5

输出:

9.45

思路和坑点

　　将月饼按照单价从高往低排序，然后遍历对每种月饼进行出售，直到需求的量被满足，或者所有的月饼都卖完。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{                    //月饼结构体 
    double num,total,price;             //总数，总价，单价 
}MC;
bool cmp(MC a,MC b){
    return a.price>b.price;             //按照单价从高到低排序 
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n;
    double d;
    scanf("%d%lf",&n,&d);               //读入数据 
    vector<MC> v(n);
    for(int i=0;i<n;i++){
        scanf("%lf",&v[i].num);
    }
    for(int i=0;i<n;i++){
        scanf("%lf",&v[i].total);
        v[i].price=v[i].total/v[i].num;
    }
    sort(v.begin(),v.end(),cmp);        //排序 
    double sum=0;
    for(int i=0;i<n;i++){               //遍历月饼数组 
        if(v[i].num>d){                 //如果需求小于库存，出售需求量即可 
            sum+=v[i].price*d;          //并将需求置0 
            d=0;
        }
        else{                           //如果，库存小于需求，则全部出售该种月饼 
            sum+=v[i].total;            
            d-=v[i].num;                //需求减小 
        }
        if(d==0) break;                 //如果循环未结束之前需求被满足，则退出循环 
    } 
    printf("%.2f",sum);                 //输出结果 
    return 0;
}