Pat class B 1020 Moon Cake

1020. The moon cake (25)

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 1 Test cases . 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 ： Arrange all moon cakes in descending order according to the unit price , Selling from high to low , If the total demand is greater than the inventory of a certain kind of moon cake , All sales , Otherwise, it will be sold according to the percentage of the remaining demand in the moon cake inventory

One 、 Starting variable

1. Structure moonCake Contains inventory , Total selling price , The unit price
2.N Types of moon cakes ,D Aggregate demand

3.sale Total sales

Two 、 operation

1. Cycle through the inventory of various mooncakes 、 Total selling price and calculate unit price

2. Sort by decreasing unit price

3. If the total demand is greater than the inventory of a certain kind of moon cake , The total sales plus the total selling price of this kind of moon cake , If the remaining total demand is less than the inventory of a certain kind of moon cake , Multiply the remaining total demand as a percentage of inventory by the total selling price of such mooncakes to sell

Code ：

//18:00
#include "stdio.h"
#include "stdlib.h"
typedef struct {
    double inventory; // stock  
    double price;  // Total selling price  
    double sigalPrice;  // The unit price  
}moonCake; 
int cmp(const void * a, const void * b);
int main()
{
    int N,D;
    scanf("%d %d",&N,&D);
    moonCake moonCakes[N];
    double sale = 0;
    for(int i = 0; i < N; i++)
    {
        scanf("%lf",&moonCakes[i].inventory); // Cycle through the inventory of various mooncakes  
    }
    for(int i = 0; i < N; i++)
    {
        scanf("%lf",&moonCakes[i].price); // Enter the selling price of various moon cakes in a cycle 
        moonCakes[i].sigalPrice = moonCakes[i].price / moonCakes[i].inventory;   // Calculate unit price  
    }
    qsort(moonCakes,N,sizeof(moonCakes[0]),cmp); // Sort by decreasing unit price  
    int i = 0;
    while(D && i != N)// When the total demand is not zero and there are still moon cakes unsold  
    {
        if(D > moonCakes[i].inventory) // The total demand is greater than i Stock of moon cakes  
        {
            sale += moonCakes[i].price;            
            D -= moonCakes[i].inventory;
        }
        else // The total demand is less than i Stock of moon cakes 
        {
            sale += moonCakes[i].price * (D / moonCakes[i].inventory);    // The remaining total demand accounts for i Multiply the percentage of mid moon cakes by the number i Stock of moon cakes , It is equivalent to that the total demand is fully satisfied D=0    
            D -= D;
        }
        i++;
    }
    printf("%.2lf",sale);
    return 0;    
} 
int cmp(const void * a, const void * b)
{
    return ((moonCake *)a)->sigalPrice > ((moonCake *)b)->sigalPrice ? -1 : 1;
}