80分,RE一个点,大佬解答关注宁(我又又又被贪心秒杀了)
查看原帖
80分,RE一个点,大佬解答关注宁(我又又又被贪心秒杀了)
146939
kkk_03_Q楼主2022/12/19 21:11
#include<bits/stdc++.h>
using namespace std;
int n,t;
double ans;
struct node{
	double m;
	double v;
	double v_;
}V[105],tmp[105];

void merge_sort(int l,int r){
	if(r-l<=1) return ;
	//如果此区域合并完成,即可结束
	int mid=l+((r-l)>>1);
	//模拟分点(这么写相比于mid=(l+r)>>1更稳定不易爆)
	merge_sort(l,mid);
	merge_sort(mid,r);
	//分别将左区和右区进行合并
	for(int i=l,j=mid,k=l;k<r;k++){
		if(j==r || (i<mid && V[i].v_>=V[j].v_)){
			tmp[k]=V[i++];
			//j==r:只剩一个元素
			//对比后发现左区首更小
		}
		else tmp[k]=V[j++];//反之
	}
	for(int i=l;i<r;i++){
		V[i]=tmp[i];//存储答案
	}
}

int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

int main(){
	n=read(),t=read();
	for(int i=0;i<n;i++){
		V[i].m=read(),V[i].v=read();
		V[i].v_=V[i].v/V[i].m;
	}
	int M=0;
	merge_sort(0,n);
	while(t!=0){
		t>=V[M].m ? ( t-=V[M].m , ans+=V[M].v) : ( ans+=V[M].v_*t , t=0);
		M++;
	}
	printf("%.2lf",ans);
	return 0;
}
/*
4 50
10 60
20 100
30 120
15 45
*/
2022/12/19 21:11
加载中...