PAT Grade B-B1020 Mooncake(25)

Mooncake is a traditional food eaten by Chinese during the Mid-Autumn Festival. There are many mooncakes with different flavors in different regions.Given the inventory of all types of mooncakes, the total selling price, and the maximum demand in the market, please calculate the maximum profit you can get.

Note: A portion of stock is allowed to be withdrawn at the time of sale.The situation given in the example is as follows: if we have 3 kinds of moon cakes, their inventory is 180,000 tons, 150,000 tons, and the total selling price is 7.5, 7.2, and 4.5 billion yuan respectively.If the maximum demand in the market is only 200,000 tons, then our maximum profit strategy should be to sell all 150,000 tons of the second type of moon cakes and 50,000 tons of the third type of moon cakes to obtain 72 + 45/2 = 9.45 billion (billion yuan).

input format:

Each input contains a test case.For each test case, a positive integer N not exceeding 1000 is given to represent the number of types of moon cakes, and a positive integer D not exceeding 500 (in 10,000 tons) represents the maximum market demand.The next line gives N positive numbers to indicate the inventory of each kind of moon cake (in 10,000 tons); the last line gives N positive numbers to indicate the total selling price of each kind of moon cake (in 100 million yuan).The numbers are separated by spaces.

Output format:

For each group of test cases, output the maximum profit in one line, in billions of yuan and accurate to 2 decimal places.

Input sample:

3 2018 15 1075 72 45

Example output:

94.50

#include#include#includeusing namespace std;struct stuff{ // cannot be named datafloat storage, total, price;} ;vector mooncake;//High unit price priority, same unit price and more stock prioritybool cmp(stuff a, stuff b){return a.price != b.price? a.price > b.price : a.storage > b.storage;}int main(){int n, d;//Type, demand, and all are positive integerscin >> n >> d;mooncake.resize(n);for(int i = 0; i < n; ++i)cin >> mooncake[i].storage;for(int i = 0; i < n; ++i){cin >> mooncake[i].total;mooncake[i].price = mooncake[i].total / mooncake[i].storage;}sort(mooncake.begin(), mooncake.end(), cmp);float ans = 0;for(int i = 0; i < n; ++i){// when inventory >= demand,if(mooncake[i].storage >= d){ans += mooncake[i].price * d;break;}ans += mooncake[i].total;d -= mooncake[i].storage;}printf("%.2f", ans);return 0;}