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

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

1 WQS 二分

1.1 概念

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

这时可以考虑 WQS 二分

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

存在函数 f(x) 在值域内为凸包，
即保证函数值域内 ∀a,b,c 满足 a<b<c， 有 f(b)−f(a)b−a<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(Tlog2⁡n)(n 是 f 值域大小)

1.2 做法

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

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

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

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

2 Codeforces 739E

2.1 题意

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

1. 消耗一个 a，答案加 pi
2. 消耗一个 b，答案加 pi
3. 消耗一个 a 和一个 b，答案加 pi+qi–piqi

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

2.2 思路

容易发现 dpi,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 参考资料

class

OI

local_offer

dp

local_offer

二分

发表评论 取消回复

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