pat之月饼问题

2024-06-19 20:18

文章标签 问题月饼 pat

本文主要是介绍pat之月饼问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有3种月饼，其库存量分别为18、15、10万吨，总售价分别为75、72、45亿元。如果市场的最大需求量只有20万吨，那么我们最大收益策略应该是卖出全部15万吨第2种月饼、以及5万吨第3种月饼，获得72 + 45/2 = 94.5（亿元）。

输入描述:

每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数、以及不超过500（以万吨为单位）的正整数D表示市场最大需求量。随后一行给出N个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出N个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出描述:

对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后2位。

输入例子:

3 2018 15 1075 72 45

输出例子:

94.50

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
struct moon
{
   double weight;
   double price;
     double priceper;
   bool operator< ( const moon& rt)
{
if(priceper>rt.priceper)
      return true;
else
      return false;
}
};
double shouyi(vector<moon>de,int d)
{   int sumwe=de[0].weight;int i=1;
    double money=de[0].price;


       while(sumwe+de[i].weight<=d)
       {
           sumwe+=de[i].weight;
           money+=de[i].price;
           i++;
       }

       money+=(d-sumwe)*de[i].priceper;
       return money;

}
int main ()

{
   int kinds,d;//D表示市场最大需求量。
   unsigned long i=0;
   vector<moon>data;
   cin>>kinds>>d;
   int kind=kinds;
   while(kinds--)
   {
       moon tem;
       cin>>tem.weight;

       data.push_back(tem);
   }
   while(kind--)
   {
       cin>>data[i].price;
       data[i].priceper=data[i].price/data[i].weight;
       if(i!=data.size()-1)
            i++;
   }
   sort(data.begin(),data.end());

   cout<<fixed<<setprecision(2)<<shouyi(data,d)<<endl;
   return 0;
}