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 );
}