[HEOI2015]小L的白日梦

第一行有一个非负整数t，表示一共有t组数据。
对于每组数据，第一行有两个非负整数n,k，分别表示你准备的项目个数和你用来陪她的天数。（n ≤ 10^5, k ≤ 10^9）
接下来n行，每一行描述一个项目，形如“x[i]/y[i] c[i]”且三个数均为非负整数，表示进行完这个项目之后她有x[i]/y[i]的概率不高兴，并且这个项目只能进行不超过c[i]次。
（x[i],y[i] ≤ 104,c[i] ≤ 10^9）

C++(g++ 7.5.0) 解法, 执行用时: 321ms, 内存消耗: 3548K, 提交时间: 2022-10-25 15:15:06

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 100100
#define double long double
const double eps=1e-10;
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
struct Node{double p;int c;}p[MAX];
bool cmp(Node a,Node b){return a.p>b.p;}
int n,K;
int main()
{
	int T=read();
	while(T--)
	{
		n=read();K=read();
		for(int i=1;i<=n;++i)
		{
			int x=read(),y=read();
			p[i].p=1.0*x/y,p[i].c=read();
		}
		sort(&p[1],&p[n+1],cmp);
		int l=1,r=n,t;
		while(!p[l].c)++l;while(!p[r].c)--r;
		p[l].c-=1;p[r].c-=1;K-=2;
		double pl=p[l].p,pr=p[r].p;
		double ans=0;
		while(K)
		{
			while(!p[l].c)++l;
			while(!p[r].c)--r;
			if(1-pl>pr)
			{
				if(fabs(pr-p[r].p)>eps)t=1;
				else t=min(K,p[r].c);
				ans+=(1-p[r].p)*pr+(t-1)*(1-p[r].p)*p[r].p;
				K-=t;p[r].c-=t;pr=p[r].p;
			}
			else
			{
				if(fabs(pl-p[l].p)>eps)t=1;
				else t=min(K,p[l].c);
				ans+=(1-pl)*p[l].p+(t-1)*(1-p[l].p)*p[l].p;
				K-=t;p[l].c-=t;pl=p[l].p;
			}
		}
		ans+=(1-pl)*pr;
		printf("%.6Lf\n",ans);
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 487ms, 内存消耗: 5688K, 提交时间: 2022-10-25 16:08:49

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n,k;
	scanf("%d %d",&n,&k);
	std::pair<long double,int> p[100010];
	for(int i=1,x,y;i<=n;i++){
		scanf("%d/%d %d",&x,&y,&p[i].second),p[i].first=1.*x/y;
		if(!p[i].second) --n,--i;
	}
	std::sort(p+1,p+n+1,std::greater());
	if(k==1) return puts("0.000000"),void();
	long double pl=p[1].first,pr=p[n].first;
	int l=1,r=n;
	k-=2,p[1].second--,p[n].second--;
	long double ans=0;
	while(k){
		while(!p[l].second) ++l;
		while(!p[r].second) --r;
		int x;
		if(pl+pr>=1){
			if(p[l].first==pl) x=std::min(k,p[l].second);	
			else x=1;
			k-=x,p[l].second-=x;
			ans+=(1-pl)*p[l].first+(x-1)*(1-p[l].first)*p[l].first;
			pl=p[l].first;
		}else{
			if(p[r].first==pr) x=std::min(k,p[r].second);
			else x=1;
			k-=x,p[r].second-=x;
			ans+=(1-p[r].first)*pr+(x-1)*(1-p[r].first)*p[r].first;
			pr=p[r].first;
		}
	}
	ans+=(1-pl)*pr;
	printf("%.6Lf\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

详情