社区讨论

贪心,样例过不了

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 条回复,欢迎继续交流。

正在加载回复...