[C++知识库]练一练「贪心的自助餐」

题目描述

小B同学想去吃自助餐，但是他是那种比较节俭的的人，既不想浪费食物，又想尽可能吃的贵一点，他于是私下里做了调查。小蓝餐厅的自助餐有?n?种食材，每种食材都有它的价格。而且也能估计出每一份的重量，所以他列了一个表格：

小BB的饭量为?C(g)，他想知道在不超过饭量的情况下他最多能吃多少钱的菜品。请你设计一个程序帮助小B计算他的最多吃了多少钱。（假设自助餐厅的菜品供应同样的菜品每个人只能取一份。）

输入描述

第一行输入两个整数n,C（0≤n≤103，0≤C≤104），其中?n?为菜品数量，C为小B的肚子容量。接下来?n?行每行输入两个数 v[i],w[i]，v[i]?是第?i?个菜品的价值，w[i]?表示第?i?个菜品的重量（0\leq v[i],w[i] \leq 10^40≤v[i],w[i]≤104）。

输出描述

输出一行数据，表示最大的价值，保留小数点后三位数。

示例

输入

20 1000
1 22
2 43
123 214
12 2
123 432
21 223
22 16
77 49
34 78
34 9
43 677
21 34
23 23
12 56
332 56
21 99
123 545
389 33
12 999
23 88

输出

1204.114

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

题目解答：?

#include <iostream>
#include<algorithm>
using namespace std;
struct node{
  double v;
  double w;
  double per;
}ve[1001];
bool cmp(struct node a,struct node b){
  return a.per>b.per;
}
int main()
{
  int n;
  double c; 
  cin>>n>>c;
  for(int i=0;i<n;i++){
    cin>>ve[i].v>>ve[i].w;
    ve[i].per=ve[i].v/ve[i].w;
  }
  sort(ve,ve+n,cmp);
  //判断全部菜品都可以装下的情况
  int sum=0;
  double value=0;
  for(int j=0;j<n;j++){
    sum+=ve[j].w;
    value+=ve[j].v;
  }
  if(sum<=c){
    printf("%.3f",value);
    return 0;
  }else{value=0;
    for(int i=0;i<n;i++){
      if(ve[i].w<=c){
        c=c-ve[i].w;
        value+=ve[i].v;
      }else{
        value+=ve[i].per*c; 
		c=0;
      }
      if(c==0) break;//装够了就跳出循环 
    }
    printf("%.3f",value);
  }
  return 0;
}