(C++)1020 月饼 简单贪心_月饼代码c++

#include<cstdio>
#include<algorithm>
using namespace std;

int types,weight;//月饼的种类数 


struct Mooncake{
	double totalPrice;
	double price;
	double weight;
	double sell;//卖出了多少 
};

bool cmp(Mooncake a,Mooncake b){
	return a.price>b.price;
}


int main(){
	
	scanf("%d%d",&types,&weight);
	Mooncake cakes[types+10];
	
	for(int i=0;i<types;i++){
		scanf("%lf",&cakes[i].weight);
	}
	for(int i=0;i<types;i++){
		scanf("%lf",&cakes[i].totalPrice);
	}
	//算出单价 
	for(int i=0;i<types;i++){
		cakes[i].price=cakes[i].totalPrice/cakes[i].weight;
	}
	
	//按照单价从高到低排序 
	sort(cakes,cakes+types,cmp);
	
	//开始贪心
	int left= weight;//还需要多少月饼
	for(int i=0;i<types;i++){
		if(cakes[i].weight<left){//当前单价最高的月饼不足以填补空缺 
			cakes[i].sell=cakes[i].weight;
			left-=cakes[i].sell;
		}else{ 
			cakes[i].sell=left;
			break;
		}
	}
	int j=0;
	double ans=0.0;
	while(cakes[j].sell!=0){
		ans+=cakes[j].price*cakes[j].sell;
		j++;
	}
		
	printf("%.2f\n",ans);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60