P4110 [HEOI2015]小L的白日梦

· · 题解

截止本文提交（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;
}