社区讨论

求助第一个点就错了

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

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lo99jes9
此快照首次捕获于
2023/10/28 07:47
2 年前
此快照最后确认于
2023/10/28 07:47
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
typedef struct {
	int m,v;
}bag; 
bool cmp (bag a ,bag b) {
	return (1.0*a.v/a.m)>(1.0*b.v/b.m);
}
int main () {
	int a,b,n,t,sum;
	cin >>n >> t;
	bag *p=new bag[n];
	for (a=0;a<n;a++) cin >> p[a].m >> p[a].v;
	sort (p,p+n,cmp);
	for (a=0;a<n;a++)  p[a].v /=p[a].m*1.0;
	for (sum=b=a=0;a<t;b++) {
		if ((a+p[b].m)>t) {
			sum=sum+(t-a)*p[b].v;
			a=t;
			break;
		} else {
			a+=p[b].m;
			sum+=p[b].m*p[b].v;
		}
		
	}
	printf ("%0.2f",sum*1.0);
} 

回复

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

正在加载回复...