PAT A1070 Mooncake (25分)

PAT A1070 Mooncake (25分)"/>

PAT A1070 Mooncake (25分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>using namespace std;
/*
给出n种不同月饼的库存量以及总售价，市场需求量d，求最大利润。
显然在要卖出总需求量为d的月饼，同时要获得最大利润的条件下，策略的选择
应该是每次先优先卖出单价高的月饼，直到卖出量等于总需求量d 思路：
1、首先定义月饼的结构体，根据题意可知其应该包含月饼的库存，总利润以及单个月饼的利润，
读入数据到结构体数组中
2、按照单个月饼的利润将数组排序，循环遍历数组，每次比较当前种类月饼的库存inventory和当前需求d的大小
若inventory小于d，则d-=inventory，并且res+=profit；否则res+=d*price，结束。 
*/
const int N=1e3+10;
struct Cake{double inventory;double profit;double price;
}cake[N];
int n,d; 
bool cmp(Cake a,Cake b){return a.price>b.price;
}
int main(){cin>>n>>d;for(int i=0;i<n;i++)cin>>cake[i].inventory;for(int i=0;i<n;i++){cin>>cake[i].profit;cake[i].price=cake[i].profit/cake[i].inventory;}sort(cake,cake+n,cmp);double res=0;for(int i=0;i<n;i++){if(cake[i].inventory<d){res+=cake[i].profit;d-=cake[i].inventory;}else{res+=cake[i].price*d;break;}}printf("%.2f\n",res); return 0;
}