贪心,样例过不了
查看原帖
贪心,样例过不了
756900
When_can_I_be楼主2022/12/3 10:40

rt

#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;
}
2022/12/3 10:40
加载中...