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;
}
更多推荐
PAT A1070 Mooncake (25分)
发布评论