模拟赛题讲解[29]

来自 s_r_f 2023-08-03 noi.ac #3197

题目描述：

小 C 打算出去旅行。

小 C 的旅行计划中，有 $n$ 个在考虑中的景点，从 $1$ 开始标号。

小 C 不想计划的过程太麻烦，所以他参观的景点编号集合一定形如 $S=\{x|x\in[l,r]\}$，即任意区间 $[l,r]$ 包含的所有编号对应的景点。

每个景点有一个 “快乐值” $a_i$ 和在该景点花费的时间 $b_i(b_i > 0)$。

一个旅行计划的快乐程度，定义为参观的景点的快乐值之和 / 时间花费总和。

小 C 打算至少旅行 $L$ 个景点，至多旅行 $R$ 个景点。他想知道他的最大快乐程度是多少。

输入格式：

第一行，三个整数 $n$ $L$ $R$

第二行，$n$ 个整数 $a_1,\cdots a_n$

第二行，$n$ 个整数 $b_1,\cdots b_n$

输出格式：

输出一行一个实数表示答案。

答案的相对误差或绝对误差不超过 $10^{-6}$ 会被判为正确答案。

输入样例：

5 2 4
100 20 1 30 30
10 1 10 2 5

输出样例：

10.9090909091

数据范围：

子任务 1(20pts) : $b_i = 1,L = 1$

子任务 2(20pts) $:$ $n \leq 2000$

子任务 3(60pts) : $n \leq 10^5,0 \leq a_i \leq 10^6,1 \leq b_i \leq 10^3, 1\leq L \leq R \leq n$

题解：

显然是 01 分数规划。我们二分这个 happy 值，然后记 $v_i = a_i - b_ix + v_{i-1}$ （注意是前缀和）

则判断就变成了：是否存在一个区间满足 $v_r \ge v_l$ 。我们可以固定右端点，维护最小的左端点（单调队列）。

时间复杂度 $\mathcal{O}\left(n \log \frac{M}{\varepsilon}\right)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
const double eps = 1e-11;
#define N ((int)(1e5 + 15))

int n,L,R,st,en,q[N]; double a[N];
struct node { int a,b; } c[N];
int dcmp(double x)
{
    if(fabs(x) <= eps) return 0;
    return x > eps ? 1 : -1; 
}
bool check(double x)
{
    for(int i = 1; i <= n; i++) a[i] = a[i - 1] + c[i].a - c[i].b * x;
    q[st = en = 0] = 0;
    for(int i = L; i <= n; i++)
    {
        if(st < en && i - q[st + 1] > R) ++st;
        while(st < en && dcmp(a[q[en]] - a[i - L]) != -1) --en;
        q[++en] = i - L;
        if(dcmp(a[i] - a[q[st + 1]]) != -1) return true;
    }
    return false;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> L >> R; cout << fixed << setprecision(10);
    for(int i = 1; i <= n; i++) cin >> c[i].a;
    for(int i = 1; i <= n; i++) cin >> c[i].b;
    double l = 0, r = 1e12;
    while(abs(r - l) >= 1e-7)
    {
        double mid = (l + r) / 2.0;
        if(check(mid)) l = mid; else r = mid;
    }
    cout << l << '\n';
    return 0;
}