题解 CF1793E Velepin and Marketing

~~时隔3年我终于又发了一篇正经题解~~

~~要不是lqr我可能这博客就卡在这里了~~

首先对所有的读者按照 $a_i$ 的大小排序

我令 $f_i$ 为当你满足前 $i$ 个读者的时候（后面的 $n - i$ 个直接摆烂，一人一本书读）的时候你最多能写多少书

然后我们考虑如何求 $f_n$

首先对于第 $n$ 个人如果我们要让他开心

我们需要至少 $a_n$ 个人和他读一本书

那么这 $a_n$ 个人

显然应该是连续，最难满足的那的 $a_n$ 个（如果不止 $a_n$ 个也是同理）

那么我们就可以写出一个转移方程

$f_n = \max\{f_1 \cdots f_{n - a_i} + 1\}$

其中需要特判一下 $a_i > i$ 的情况，这种时候你需要把让 $a_i$ 个人全都读一本书同时后面摆烂的人会变成 $n - a_i$ 个

这个方程可以简单通过一个前缀最大和来实现

最后把根据 $f_i$ 算出写若干本书的时候可以满足的读者数量（我的代码里多了一个 $h_i$ 用来合并 $a_i > i$ 的情况）

#include<bits/stdc++.h>

int inp(){
    char c = getchar();
    while(c < '0' || c > '9')
        c = getchar();
    int sum = 0;
    while(c >= '0' && c <= '9'){
        sum = sum * 10 + c - '0';
        c = getchar();
    }
    return sum;
}

int a[300010], f[300010], g[3000010], ans[300010], h[300010];

int main(){
    int n = inp();
    for(int i = 1; i <= n; i++)
        a[i] = inp();
    std::sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        f[i] = (a[i] > i) ? 0 : (g[i - a[i]] + 1);
        h[i] = (a[i] > i) ? (n - a[i] + 1) : (f[i] + n - i);
        g[i] = std::max(f[i], g[i - 1]);
    }
    for(int i = 1; i <= n; i++)
        if(h[i] > 0)
            ans[h[i]] = i;
    for(int i = n - 1; i >= 1; i--)
        if(ans[i] < ans[i + 1])
            ans[i] = ans[i + 1];
    int q = inp();
    for(int i = 1; i <= q; i++)
        printf("%d\n", ans[inp()]);
}

Dilute

题解 CF1793E Velepin and Marketing