74-贪心-买月饼

　　　　　　　　　　　　　　　　　　　　　　　　　　　　1454.贪心题-月饼 (10分)

C时间限制：3000 毫秒 | C内存限制：3000 Kb

题目内容：

 现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。
注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有3种月饼，其库存量分别为18、15、10万吨，总售价分别为75、72、45亿元。

输入描述

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

输出描述

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

输入样例

3 20 18 15 10 75 72 45

输出样例

94.50

好久没写题了，犯了很低级的错误，二且一直未发现，可怕

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef struct node{
  double w, v;
  double danjia;
}node;
node a[1005];
bool cmp(node x, node y){
  if(x.danjia > y.danjia)
    return 1;
  else
    return 0;
}
int main()
{
  int n, m;
  cin >> n >> m;
   
  for(int i = 0; i < n; i++){
    cin >> a[i].w;
  }
  if(m == 0){
  	cout << 0 <<endl;
  	return 0;
  }
  for(int i = 0; i < n; i++){
    cin >> a[i].v;
    a[i].danjia = a[i].v / a[i].w;
  }
  sort(a, a + n, cmp);
  int k = 0;
  double sum = 0;
  while(m > 0){
    if(m >= a[k].w){
      sum += a[k].v;
      m -= a[k].w;
      k++;
//      continue;    //这里如果用continue会导致m>所有价格时一直购买，a[]越界,对于为什么没报错，是因为a[]定义的比较大，虽然k>n但是小于1005 
    }
    if(m < a[k].w){
      sum += a[k].danjia * m;
      m = 0;
    }
    if(k >= n){
    	break;
    }
  }
  //cout << sum << endl;
  printf("%.2lf\n", sum);
  return 0;
}

74-贪心-买月饼

推荐阅读