题解：CF1793E Velepin and Marketing

· · 题解

原题题意等价于 n 个点分为 k 组，设第 i 个点所在组的长度为 l_i，则总贡献为 \sum\limits_{i=1}^n [a_i\le l_i]。不难发现，分组越多，贡献越小，所以我们考虑枚举贡献，对于每一种贡献确定分组的上限。不难发现，对于相同的贡献，肯定是贪心地考虑 a_i 更小的，这样的 a_i 才更容易被满足。所以考虑对 a 排序，每次取一段前缀，计算假设这段前缀都被满足的分组上限。

继续贪心地想，对于满足一段前缀合法如何使得分组数量最大。要满足前缀合法就可能往后取，由于后面的数字不用考虑贡献，没有被选中的那些人都可以每人分一组，后面多保留一个一定不劣与前面多保留一个的贡献，所以贪心策略就转化成了考虑保留尽量多的后面的数的情况下，最小化前面数字分组数。我们记 f_i 表示前 i 个数都合法的最大分组数。考虑 a_i>i，前面的数字必须分为一组，并且会影响到一些后面的数，所以 f_i=n-a_i+1。否则就考虑将 i 作为当前 i 所在组的最后一个数，前面的 a_i-1 个数也都要分到这一组里。由于 a_i 单调不降，所以前面的数划分到当前组肯定也是合法的。我们再记 g_i 表示保证 i 之前都合法，且不会将 i 之后的数都划分进去的最大分组数。在 a_i\le i 的情况下 f_i 就是 g_{i-a_i}+1+n-i，表示 i-a_i 之前的划分最大方案 + i-a_i+1\sim i 划分为一段的贡献 + 后面 n-i 个数单独划分的贡献，同时 g_i=g_{i-a_i}+1，并将 g_i 取前缀 \max。

得到 f 数组之后就双指针枚举贡献及最大分组数，将 f_i 与 i 的对应关系给映射到 ans 数组中，询问的时候直接查询即可。但是注意分组数的上限为 n-a_1+1，再多的分组答案就为 0 了。排序使用桶排，时间复杂度 O(n)。

code：

const int N=3e5+5;
int n,m,a[N],f[N],g[N],ans[N],q,cnt[N];
inline void SOLVE(){
    n=rd();for(int i=1;i<=n;i++)++cnt[rd()];
    for(int i=1;i<=n;i++)while(cnt[i])cnt[i]--,a[++m]=i;
    for(int i=1;i<=n;i++){
        if(a[i]<=i)f[i]=g[i-a[i]]+1+n-i,g[i]=g[i-a[i]]+1;
        else f[i]=n-a[i]+1,g[i]=0;cmx(g[i],g[i-1]);
    }for(int i=1,j=n-a[1]+1;i<=n;i++){
        if(f[i]==f[i+1])continue;
        while(j>f[i+1])ans[j]=i,j--;
    }q=rd();while(q--){int x=rd();printf("%lld\n",ans[x]);}
    return ;
}