PTA TIANTI game exercise set l2-003 moon cake test point 2, test point 3 Analysis

The moon cake

Moon cake is a kind of traditional food that Chinese people eat during the Mid Autumn Festival , There are many different flavors of moon cakes in different regions . Now, the inventory of all kinds of mooncakes is given 、 Total selling price 、 And the biggest demand in the market , Please calculate the maximum profit you can get .

Be careful ： Allow to take out part of the inventory when selling . The example shows this ： If we have 3 Mooncakes , The inventory is 18、15、10 Ten thousand tons of , The total selling price is 75、72、45 One hundred million yuan . If the market's maximum demand is only 20 Ten thousand tons of , Then our biggest revenue strategy should be to sell all 15 Ten thousand tons 2 Mooncakes 、 as well as 5 Ten thousand tons 3 Mooncakes , get 72 + 45/2 = 94.5（ One hundred million yuan ）.

Input format ：
Each input contains a test case . Each test case shall be provided with no more than one 1000 The positive integer N Number of moon cakes 、 And not more than 500（ In 10000 tons ） The positive integer D Represents the maximum market demand . The next line shows N A positive number indicates the stock of each kind of moon cake （ In 10000 tons ）; The last line gives N A positive number indicates the total selling price of each kind of moon cake （ In 100 million yuan ）. Numbers are separated by spaces .

Output format ：
For each group of test cases , Output maximum revenue in one line , In hundred million yuan and accurate to the decimal point 2 position .

sample input ：

3 20
18 15 10
75 72 45

sample output ：

94.50

Ideas ： Use the structure to save the inventory of moon cakes 、 Total selling price and unit price . In this question, the higher the unit price of moon cakes, the more income . Each element of the structure array is a kind of moon cake . So use the moon cake unit price to sort the structure array , Put the mooncakes with high unit price in front . Start filling the market with mooncakes with high unit prices , In this way, the total income is high .

Be careful ： Each test case is given a No more than 1000 Of Positive integer N Number of moon cakes 、 as well as No more than 500（ In 10000 tons ） Of Positive integer D Represents the maximum market demand . The next line shows N It's a positive number Represents the inventory of each kind of moon cake （ In 10000 tons ）; The last line gives N A table of positive numbers Show the total selling price of each kind of moon cake （ In 100 million yuan ）

The title states that the inventory and total selling price are N It's a positive number So it's not necessarily an integer , It could be floating point numbers

AC Code （C++)

#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

struct yuebing
{
    
	double kucun;			//  stock 
	double zongshoujia;     //  Total selling price 
	double danjia;			//  The unit price 
};

bool cmp(struct yuebing a, struct yuebing b)
{
    
	//  Top of the list with high unit price 
	return a.danjia > b.danjia;
}

int main()
{
    
	int num;				//  Types of moon cakes 
	int maxNeed;			//  Maximum market demand 

	cin >> num >> maxNeed;

	//  Dynamic application space 
	struct yuebing* ptr = new struct yuebing[num];

	for (int i = 0; i < num; i++)
		cin >> ptr[i].kucun;
	for (int i = 0; i < num; i++)
	{
    
		cin >> ptr[i].zongshoujia;

		//  Calculate the unit price of moon cakes 
		ptr[i].danjia = double(ptr[i].zongshoujia) / ptr[i].kucun;
	}
	//  Arrange in descending order with the unit price of moon cakes 
	sort(ptr, ptr + num, cmp);

	int k = 0;				//  Used to traverse the structure 
	double ans = 0;			//  Save the calculated results 
	while (maxNeed > 0)		//  Continue to calculate when the market demand is not met 
	{
    
		//  The market demand is not satisfied, but all kinds of moon cakes have been sold out 
		if (k >= num)
			//  There are no moon cakes, so stop calculating 
			break;
		
		//  The current kind of moon cake inventory can meet the market demand 
		if (maxNeed < ptr[k].kucun)
		{
    
			//  Subtract the last batch of moon cakes from the inventory , In this problem, this line of code is meaningless 
			ptr[k].kucun -= maxNeed;
			//  Calculate the income of the last batch of moon cakes and add the total income 
			ans += ptr[k].danjia * maxNeed;
			//  The last batch of moon cakes have been sold, and the market demand is 0
			maxNeed = 0;
		}
		else
		{
    
			//  Put all the inventory of current moon cakes into the market , Reduce market demand 
			maxNeed -= ptr[k].kucun;
			//  Add the total income of the current moon cake to the total income of the statistics 
			ans += ptr[k].zongshoujia;
		}
		k++;			//  Traverse the moon cake type structure 
	}
	
	//  Leave two digit dots 
	cout << fixed << setprecision(2) << ans;

	return 0;
}

Test point 2： Floating point number of inventory
Different friends can try the following test data .
Input ：

3 20
18.2 15.4 10
75.6 72.7 45.6

Output ：

90.94

Test point 3： The market demand is greater than the total inventory of all moon cakes , That is to say, selling all moon cakes cannot meet the market demand
If there is a segment error, you can try the following test data
Input ：

3 200
18.2 15.4 10
75.6 72.7 45.6

Output ：

193.90