WQS 二分入门 – Codeforces 739E

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$,对于每一位,你有三个选择

  1. 消耗一个 $a$,答案加 $p_i$
  2. 消耗一个 $b$,答案加 $p_i$
  3. 消耗一个 $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 );
}

3 参考资料

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

message
account_circle
Please input name.
email
Please input email address.
links

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据