自动搬运

查看原文

来自洛谷，原作者为

	gxy001 ......

搬运于2025-08-24 21:56:36，当前版本为作者最后更新于2022-04-02 11:48:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

截止本文提交（2022.4.2）前，洛谷题解区的三篇博客证明均为错误的，希望管理员看到后撤掉。

因为期望的线性性，答案即为 $\sum\limits_{i=2}^k(1-a_{i-1})a_{i}$。

题意可以理解为，给 $m=\sum c_i$ 个 $[0,1]$ 间的实数，从中选出 $k$ 个排成一个序列 $a$，最小化 $\sum\limits_{i=2}^k(1-a_{i-1})a_{i}$，假设 $k\ge 2$。

引理 1：选出的 $k$ 个数按照单调不增排列。

这里需要注意的是，网传的对于降序数组交换两个数后证明答案变大的证法是绝对错误的，这只能证明降序数组要优于降序数组交换两个数的答案，不能证明降序数组比其他所有情况更优，属于是学 exchange argument 没学会还乱用了。

假设我们已经选定 $k$ 个数为 $a_1,\cdots,a_k$，要为这些数定序，此时 $\sum a_i$ 是定值，题目要求最小化 $\sum\limits_{i=2}^k(a_i-a_{i-1}a_{i})$，我们可以转为最大化 $\sum\limits_{i=1}^ka_i-\sum\limits_{i=2}^k(a_i-a_{i-1}a_{i})=1\times a_1+\sum\limits_{i=2}^ka_{i-1}a_{i}$。

假设 $a$ 降序排序后的数组为 $b$。

由排序不等式得 $1\times a_1+\sum\limits_{i=2}^ka_{i-1}a_{i}\le 1\times b_1+\sum\limits_{i=2}^kb_{i-1}b_{i}$，所以选出的 $k$ 个数一定按照单调不增排列。

引理 2：选出的 $k$ 个数是所有数降序排序后的一段前缀加一段后缀。

我们设选择的数下标按顺序为 $i_1,\cdots,i_k$，所有 $m$ 个数排序后的数列为 $x$。

若$i_1\ne 1$，显然有 $(1-x_1)x_{i_2}\le(1-x_{i_1})x_{i_2}$，所以我们可以令 $i_1=1$。

若$i_k\ne m$，显然有 $(1-x_{i_{k-1}})x_m\le(1-x_{i_{k-1}})x_{i_k}$，所以我们可以令 $i_k=m$。

所以一定会选择一段前缀和一段后缀。

假设至少存在一个数不属于前缀或后缀。

不失一般性地，我们设选择的前缀为 $1\sim l$，选择的后缀为 $m-r+1\sim m$。

考虑将 $i_{l+1}$ 替换为 $l+1$，此时答案会变化 $(1-x_{l})x_{l+1}+(1-x_{l+1})x_{i_{l+2}}-(1-x_{l})x_{i_{l+1}}-(1-x_{i_{l+1}})x_{i_{l+2}}=(1-x_l-x_{i_{l+2}})(x_{l+1}-x_{i_{l+1}})$，由于 $x_{l+1}\ge x_{i_{l+1}}$，所以当 $1-x_l-x_{i_{l+2}}\le 0$ 时，替换不会更劣。

考虑将 $i_{k-r}$ 替换为 $m-r$，此时答案会变化 $(1-x_{i_{k-r-1}})x_{m-r}+(1-x_{m-r})x_{m-r+1}-(1-x_{i_{k-r-1}})x_{i_{k-r}}-(1-x_{i_{k-r}})x_{m-r+1}=(1-x_{i_{k-r-1}}-x_{m-r+1})(x_{m-r}-x_{i_{k-r}})$，由于 $x_{m-r}\le x_{i_{k-r}}$，所以当 $1-x_{i_{k-r-1}}-x_{m-r+1}\ge 0$ 时，替换不会更劣。

接下来只需证明 $x_l+x_{i_{l+2}}\ge 1$ 和 $x_{i_{k-r-1}}+x_{m-r+1}\le 1$ 必有一个成立，那么我们就可以进行若干次调整，将不在前后缀上的数都放到前缀或后缀上，显然调整在有限步内一定结束。

显然有 $x_l+x_{m-r+1}\ge 1$ 和 $x_l+x_{m-r+1}\le 1$ 必有一个成立。

若 $x_l+x_{m-r+1}\ge 1$ ，由于 $x_{i_{l+2}}\ge x_{m-r+1}$，所以 $x_l+x_{i_{l+2}}\ge 1$ 成立。

若 $x_l+x_{m-r+1}\le 1$ ，由于 $x_{i_{k-r-1}}\le x_l$，所以 $x_{i_{k-r-1}}+x_{m-r+1}\le 1$ 成立。

在知道这两个性质后这道题就可以做了， $x_1$ 和 $x_m$ 必选，维护当前选择的前缀和后缀，利用引理 2 中的式子判断当前应该扩大前缀还是后缀，由于选择相等的数不会改变 $x_l+x_{m-r+1}$，所以一次可以把相等的数全选了，复杂度瓶颈在排序 $O(n\log n)$。

#include<cstdio>
#include<algorithm>
#include<functional>
#include<utility>
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;
}