题解：P4653 [CEOI2017] Sure Bet

· · 题解

前言 & 吐槽

@Seauy 大佬的题解说二分做不了，但其实是可以的。

题面中将灯泡分组的说法具有误导性，实际上不用管这个分组，任意选就行。

思路 & 解析

“最小值最大”是二分答案的经典标志，问题答案具有二段性：在最大的最小值以前，一定有方法使收益达到或超过目标，以后则一定不可能达到。

二分这个最大的最小可能收益 mid。如果有某种方法可以使两类灯泡都能大于等于这个最小可能收益，那么比它小的也都能达到，l=mid；否则如果不存在这样的方法，比它大的都达不到，r=mid。

附一个浮点数二分模板：

const double EPS=1e-6;
double l=0,r=2e8;
while(r-l>EPS)
{
  double mid=(l+r)/2;
  if(check(mid)) l=mid;
  else r=mid;
}

问题的关键在于如何找这个方法，即 check 函数怎么写。

贪心的思路，如果要在某一类中选灯泡，选灯泡的代价都一样，那么一定是优先选权值高的灯泡。所以，我们将灯泡按照权值从大到小排序，并预处理出排序后的前缀和。

那么我们就可以枚举一共选择的灯泡数量 i，这样对于每一类灯泡，都必须保证选择灯泡的权值和减去 i 大于等于 mid，即权值和大于等于 mid+i。

然后在每一类灯泡中，选出最少的灯泡使其满足权值和大于等于 mid+i，这个可以直接在刚才预处理的前缀和数组上跑二分查找。

最后，如果两类所需要的灯泡数量小于等于 i（在灯泡数量限制内可以选出足够满足条件的灯泡），这个 mid 就是可行的。否则若无论选择多少个灯泡都不能满足条件，这个 mid 就是不合法的。

时间复杂度 O(\log \frac{n V}{\epsilon} \times n \log n)，V 表示 A,B 的值域，\epsilon 表示精度（即上面模板中的 EPS）。

代码 & 细节

一共有 2n 个灯泡，枚举选择灯泡数量的时候别写成 n 了。

如果二分查找满足条件的最少灯泡时发现无法使权值和大于等于 mid+i，代表即便全选也依然小于要求的下限 mid，此时已经不可能合法了。后面更大的 i 更不可能找到合法选择方案，所以这里直接 break 掉就行了。

代码：

#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;

const int N=1e5+5;
int n;
double a[N],b[N];
double suma[N],sumb[N];

bool check(double flr)
{
    for(int i=1;i<=n<<1;i++) //注意要乘2
    {
        int mna=lower_bound(suma+1,suma+n+1,flr+i)-suma;
        int mnb=lower_bound(sumb+1,sumb+n+1,flr+i)-sumb;
        if(mna>n||mnb>n) return false;
        //判断越界（找不到可行解），后面再也不可能有解了
        if(mna+mnb<=i) return true; //判断条件==和<=均可通过
    }
    return false;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&a[i],&b[i]);
    sort(a+1,a+n+1,greater<double>()); //从大到小排序，下同
    sort(b+1,b+n+1,greater<double>());
    for(int i=1;i<=n;i++) //预处理前缀和
    {
        suma[i]=suma[i-1]+a[i];
        sumb[i]=sumb[i-1]+b[i];
    }
    const double EPS=1e-6;
    double l=0,r=2e8;
    while(r-l>EPS)
    {
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.4lf\n",l);
    return 0;
}

后记 & 扩展

此方法可以很轻松地扩展为“k 类灯泡”问题（时间复杂度乘个 k），而 O(n) 的直接贪心则做不到。