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