原题
Mooncake is a Chinese bakery product traditionally eaten during the Mid-Autumn Festival. Many types of fillings and crusts can be found in traditional mooncakes according to the region's culture. Now given the inventory amounts and the prices of all kinds of the mooncakes, together with the maximum total demand of the market, you are supposed to tell the maximum profit that can be made.
Note: partial inventory storage can be taken. The sample shows the following situation: given three kinds of mooncakes with inventory amounts being 180, 150, and 100 thousand tons, and the prices being 7.5, 7.2, and 4.5 billion yuans. If the market demand can be at most 200 thousand tons, the best we can do is to sell 150 thousand tons of the second kind of mooncake, and 50 thousand tons of the third kind. Hence the total profit is 7.2 4.5/2 = 9.45 (billion yuans).
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integersN(≤1000), the number of different kinds of mooncakes, andD(≤500thousand tons), the maximum total demand of the market. Then the second line gives the positive inventory amounts (in thousand tons), and the third line gives the positive prices (in billion yuans) ofNkinds of mooncakes. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the maximum profit (in billion yuans) in one line, accurate up to 2 decimal places.
Sample Input:
3 200 180 150 100 7.5 7.2 4.5结尾无空行
Sample Output:
9.45结尾无空行
思路
这个问题的想法很简单，优先考虑昂贵的月饼。
通过代码
学习了柳神的格式，整齐地看着很酷。
#include <bits/stdc .h> using namespace std; typedef pair <double ,double> mooncake; bool cpm(mooncake a,mooncake b){ return a.second/a.first>b.second/b.first;///按价格从贵到便宜排序 } int main(){ double profit=0; int n,amount; scanf("%d%d",&n,&amount); vector <mooncake> cakes(n); for(int i=0;i<n;i )scanf("%lf",&cakes[i].first); for(int i=0;i<n;i )scanf("%lf",&cakes[i].second); sort(cakes.begin(),cakes.end(),cpm); for(int i=0;i<n;i ){ if(cakes[i].first<amount){ amount-=cakes[i].first; profit =cakes[i].second; }else{ profit =cakes[i].second*amount/cakes[i].first; break; } } printf("%.2f",profit); return 0; }总结
知识
vector虽然是可变数组，但如果后面真的不接长度，就无法访问，会报错，提示越界。
vector <pair <double ,double> > cakes; for(int i=0;i<n;i ){...}//会报错的 vector <pair <double ,double> > cakes (n);//n已读入的整数 for(int i=0;i<n;i ){...}//正确- 注意以下写法
它定义了一个名字mooncake变量，不能在vector<>将变量名放入其中，只能放:pair < int, double > mooncake; vector <mooncake> cakes;//错误的
在迭代器中使用复杂的数据类型，也建议使用上述方法，避免麻烦，方便修改。typedef pair < int ,double > mooncake; vector <mooncake> cakes; -
对于以下常见的单句循环，建议用第一种方法代替第二种方法：
for(int i=0;i<n;i )scanf("%lf",&cakes[i].first);//1 for(int i=0;i<n;i ){ scanf("%lf",&cakes[i].first); }//2这样，代码高度更短，浏览更方便。
心态
- 首先我题就没看懂，因为我潜意识里默认price是每种月饼的单价（ billion yuan/thousand ton），然后我就不太明白为什么我先在例子买7.2而不是7.5.然后加两个单价？？？然后我去搜索别人的博客了解这里price是月饼的总价(其实结合常识常识知道，如果是7.2billion yuan/thousand ton，7200元/kg，不应该很常见/应该不应该很常见/应该不应该很常见/应该不应该很常见/应该不应该很常见/应该不应该不应该很常见/应该不应该很常见/应该不应该不应该很常见/应该不应该不应该不应该很常见/应该不应该不应该不应该不应该不应该很常见/应该不应该不应该不应该不应该不应该很常见/应该不应该不应该不应该不应该不应该不应该很常见/应该不应该不应该不应该不应该不应该不应该不应该很常见/应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该很常见/应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该很常见/应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该很常见/应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该很常见/应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该很常见/应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该不应该doge），下次看题请结合例子认真理解题意。
- 问题很坑人的一点是市场需求是用来的positive integers，例如，每个月饼的数量也是正的和正的。我自然认为每个月饼的数量（更不用说粗心了）都是int类型，只有部分正确(23/25)跑出来，改成double立刻全对。记住，以后每次做题都要看清楚每个数据的类型，写完之后如果有问题就检查自己判断的数据类型是否有误。