社区讨论
求助第一个点就错了
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 条回复,欢迎继续交流。
正在加载回复...