社区讨论

AC#1求掉

P2240【深基12.例1】部分背包问题参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mli2uh3z
此快照首次捕获于
2026/02/11 21:40
上周
此快照最后确认于
2026/02/11 22:45
上周
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
struct gold{
	double j;
	int k,v;
}golden_coin[1000];
bool cmp(gold a,gold b){
	return a.j>b.j;
}
double sumj,sumv;
int main(){
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,ma;
	cin>>n>>ma;
	 for(int i=0;i<n;i++){
	 	cin>>golden_coin[i].k>>golden_coin[i].v;
	 	golden_coin[i].j=golden_coin[i].v/golden_coin[i].k;
	 }
	 sort(golden_coin,golden_coin+n,cmp);
	for(int i=0;i<n;i++){
		if(sumv+golden_coin[i].k<=ma){
			sumv+=golden_coin[i].k;
			sumj+=golden_coin[i].v;
			continue;
		}
		if(sumv+golden_coin[i].k>ma){
			double bs=(ma-sumv)/golden_coin[i].k;
			sumj+=golden_coin[i].v*bs;
		}
	}cout<<fixed<<setprecision(2)<<sumj;
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...