社区讨论
贪心,样例过不了
P2240【深基12.例1】部分背包问题参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo7eudvu
- 此快照首次捕获于
- 2023/10/27 00:40 2 年前
- 此快照最后确认于
- 2023/10/27 00:40 2 年前
rt
CPP#include<iostream>
#include<math.h>
#include<iomanip>
#include<cstring>
using namespace std;
int main(){
int N,T,x;//N:堆数 T:背包剩余空间 x:对下标进行标记
cin>>N>>T;
double s[2][N],cnt=0,max=-114514;//s[0][i] :金币质量 s[1][i]:金币价值 cnt:计算当前背包中金币价值
for(int i=0;i<N;i++){
cin>>s[0][i]>>s[1][i];
s[1][i]/=s[0][i];//输入的同时将金币总价值换算为单价
}
for(;;){
for(int i=0;i<N;i++){
if(s[1][i]>=max){
max=s[1][i];
x=i;//取价值最大的金币并标记
}
}
if(s[0][x]<=T){//判断当前价值最大的金币质量是否大于背包剩余部分
cnt+=s[1][x]*s[0][x];
T-=s[0][x];
s[1][x]=-114514;
max=-114514;
}else{
cnt+=s[1][x]*(s[0][x]-T);
cout<<fixed<<setprecision(2)<<cnt;
return 0;
}
}
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...