WQS 二分入门 - Codeforces 739E

发布于 2021-07-01 # algorithm

0 碎碎念

实数二分，永远的调不出来(｡◕∀◕｡)

但是这算法还挺有意思的，故写到博客

1 WQS 二分

1.1 概念

一部分题目会有一个限制条件使得本来可以 $O(n)$ 解决问题需要再 $O(nk)$ 的复杂度解决

这时可以考虑 WQS 二分

WQS 是解决形如以下的问题：

存在函数 $f(x)$ 在值域内为凸包，即保证函数值域内 $\forall a,b,c$ 满足 $a<b<c$ ，有 $\frac{f(b)-f(a)}{b-a} <\frac{f(c)-f(b)}{c-b}$

我们不能快速求出 $f(x)$ ，但我们可以知道 $g(x) = kx + b$ 与 $(x,f(x))$ 有没有交点。

因为 $f(x)$ 是凸壳，满足斜率单调递减，故 $g(x)$ 与 $(x,f(x))$ 是否相交关于 $k$ 单调，故可以二分求 $k$ 。

随后是怎么确定 $b$ 的问题，对于函数 $g(x)$ 来说，其截距就是 $f(x) - kx$ ，令计算 $f(x)-kx$ 的时间复杂度为 $T$

则这个算法的时间复杂度为 $O(T\log_2n)$ ( $n$ 是 $f$ 值域大小)

1.2 做法

感性理解则是给定 $n$ 个物品，有权重 $w_i$ ，选择 $k$ 个，求最大权值。

容易发现没有 $k$ 的限制很容易在 $O(n)$ 内求出答案。

注意到如果给每个权重加一个 $x$ ，则 $x$ 上涨时选择的数量会下降，即构成单调性。

故可以二分 $x$ 使得此时恰好选择 $k$ 个，此时答案救为我们所求。

2 Codeforces 739E

2.1 题意

给定两个序列 $p,q$ ，对于每一位，你有三个选择

消耗一个 $a$ ，答案加 $p_i$
消耗一个 $b$ ，答案加 $p_i$
消耗一个 $a$ 和一个 $b$ ，答案加 $p_i + q_i - p_iq_i$

$a,b$ 均有使用上限，求最大答案。

2.2 思路

容易发现 $dp_{i,j,k}$ 随便做

容易发现 $j,k$ 两位都是凸壳

套两层 WQS 二分即可

2.3 Code

/*
 * e.cpp
 * Copyright (C) 2021 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU AGPLv3+ license.
 */

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>

typedef long long ll;
typedef unsigned long long ull;

const int N = 2100;
const double eps = 1e-7;

inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
template <class T>
T Max( T a, T b ) { return a > b? a: b; }
template <class T>
T Min( T a, T b ) { return a < b? a: b; }
template <class T>
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T>
void chk_Min( T &a, T b ) { if( b < a ) a = b; }
template <typename T>
T read() {
    T sum = 0, fl = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
    return sum * fl;
}
template <class T>
T pow( T a, int p ) {
    T res = 1;
    while( p ) {
        if( p & 1 )
            res = res * a;
        a = a * a;
        p >>= 1;
    }
    return res;
}/*}}}*/

double p[N], u[N];
int n, limit_a, limit_b;

struct CheckRes { bool right; double val; };

double f[N];
int cnt_a[N], cnt_b[N];
CheckRes check_a( double offset_a, double offset_b ) {
    for( int i = 0; i <= n; i ++ ) {
        f[i] = 0; cnt_a[i] = cnt_b[i] = 0;
    }
    for( int i = 1; i <= n; i ++ ) {
        const double cost_a = p[i] - offset_a, cost_b = u[i] - offset_b;
        f[i] = f[ i - 1 ];
        cnt_a[i] = cnt_a[ i - 1 ]; cnt_b[i] = cnt_b[ i - 1 ];
        if( f[ i - 1 ] + cost_a - f[i] > eps ) {
            f[i] = f[ i - 1 ] + cost_a;
            cnt_a[i] = cnt_a[ i - 1 ] + 1;
            cnt_b[i] = cnt_b[ i - 1 ];
        }
        if( f[ i - 1 ] + cost_b - f[i] > eps ) {
            f[i] = f[ i - 1 ] + cost_b;
            cnt_a[i] = cnt_a[ i - 1 ];
            cnt_b[i] = cnt_b[ i - 1 ] + 1;
        }
        if( f[ i - 1 ] + cost_a + cost_b - u[i] * p[i] - f[i] > eps ) {
            f[i] = f[ i - 1 ] + cost_a + cost_b - u[i] * p[i];
            cnt_a[i] = cnt_a[ i - 1 ] + 1;
            cnt_b[i] = cnt_b[ i - 1 ] + 1;
        }
    }
    return (CheckRes) { cnt_a[n] >= limit_a, f[n] + offset_b * limit_b + offset_a * limit_a };
}

CheckRes check_b( double offset_b ) {
    double left = 0, rig = 1, offset_a = 0;
    while( left + eps <= rig ) {
        double mid = ( left + rig ) / 2.0;
        CheckRes res = check_a( mid, offset_b );

        if( res.right ) {
            offset_a = mid;
            left = mid + eps;
        }
        else
            rig = mid - eps;
    }

    check_a( offset_a, offset_b );

    return (CheckRes) { cnt_b[n] >= limit_b, f[n] + offset_b * limit_b + offset_a * limit_a };
}

int main() {
#ifdef woshiluo
    freopen( "e.in", "r", stdin );
    freopen( "e.out", "w", stdout );
#endif
    scanf( "%d%d%d", &n, &limit_a, &limit_b );
    for( int i = 1; i <= n; i ++ ) {
        scanf( "%lf", &p[i] );
    }
    for( int i = 1; i <= n; i ++ ) {
        scanf( "%lf", &u[i] );
    }

    double left = 0, rig = 1, offset_b = 0;
    while( left + eps <= rig ) {
        double mid = ( left + rig ) / 2.0;
        CheckRes res = check_b(mid);

        if( res.right ) {
            offset_b = mid;
            left = mid + eps;
        }
        else
            rig = mid - eps;
    }

    printf( "%.4lf", check_b(offset_b).val );
}