1点过,其余WA,求助大佬!
查看原帖
1点过,其余WA,求助大佬!
1123382
asezllh楼主2024/6/11 17:50
#include<bits/stdc++.h>
using namespace std;
int m[1005],v[1005],m1[1005],v1[1005];
double num[1005],t[1005];

//排序
void Sort(int l,int r){
	if(l>=r) return;
	
	int mid=(l+r)/2;
	Sort(l,mid),Sort(mid+1,r);
	
	int i=l,j=mid+1,k=l;

	while(i<=mid && j<=r){
		if(num[i]<=num[j]){t[k]=num[i];m1[k]=m[i];v1[k]=v[i];i++,k++;}

		else{t[k]=num[j];m1[k]=m[j];v1[k]=v[j];j++,k++;}
	}
	
	while(i<=mid) {t[k]=num[i];m1[k]=m[i];v1[k]=v[i];i++,k++;}
	
	while(j<=r) {m1[k]=m[j];v1[k]=v[j];t[k++]=num[j++];}
	
	for(int i=l;i<=r;i++) {num[i]=t[i];m[i]=m1[i];v[i]=v1[i];}
}

int main(){
	int N,T;
	cin>>N>>T;
	
	for(int i=1;i<=N;i++)
		cin>>m[i]>>v[i];
	
	//计算每份物品的平均价值(性价比)
	for(int i=1;i<=N;i++){
		num[i]=v[i]/m[i];
	}
	
//	for(int i=1;i<=N;i++) cin>>num[i];
	
	Sort(1,N);
	
	int tt=0,i=N+1;
	double ans=0;
	while(tt<T && i>=1){
		i--;
		tt+=m[i];
		ans+=v[i];
	}
	
	if(tt>T){
		tt-=m[i],ans-=v[i];
		double a=T-tt,b=v[i]/m[i];
		ans+=a*b;
	}
	
	printf("%.2lf",ans);
	
//	for(int i=1;i<=N;i++) cout<<num[i]<<" "<<m[i]<<" "<<v[i]<<endl;
	
	return 0;
}
2024/6/11 17:50
加载中...