首先发现，每个人过的题是不同的，所以我们不关心过了那些题目。
我们要直接去求分成 \(k\) 组最多的通过数是不容易的。我们可以转换一下，求当 \(i\) 个题通过的时候 __最多__分多少组。为什么记最多，因为化成 \(k\) 个组通过 \(i\) 题可以的情况下，我们可以任意合并两个组，保证依然可以通过 \(i\) 个题。相当于求了上界，方便求答案。
目前已知，要求：当 \(i\) 个题通过的时候 最多分多少组 。
我们考虑记两个内容 ：
\(F_i\) ：表示通过前 \(i\) 个题分成了多少组（只关心前 \(i\) 个被分成了多少组）。
\(G_i\) ： 表示通过前 \(i\) 个题最少用了多少个人（因为会有后面的拿来充数）。
介绍一下定义，我们要求的其实是一个 \(ans\) 表示 \(i\) 个分组最多通过几道题。因为我求了 \(F_i\) 和 \(G_i\) ，所以我们可以得到所有的人被分成了多少组。即 \((n - G_i) + F_i\) 。将 \(ans_{(n - G_i) + F_i}\) 赋值为 \(i\) ,同时 \(ans_i = \max(ans_i,ans_{i-1})\)。这样就求出了 \(ans\) 数组。
当前可能 \(F_i\) 和 \(G_i\) 记录的情况可能不止过了 \(i\) 道题。但在后面会重新被更改为最大的，所以不影响答案。
关于转移。我们知道将排序后连续一段放在一个组别中一定最优。因为当花费了 \(a_i\) 个人帮助 \(i\) 个人完成了题目，但 \(i-1\) 不在，所以有要花费 \(a_{i-1}\) 来完成第 \(i-1\) 个题目，这显然不优。其次，我们转移中，\(G_i\) 越小转移越优。因为 \(G_i\) 越大那么没用的越少，我们要求最多没用的一定是单个单个分开，所有 \(G_i\) 越大一定不比自己小的优。在 \(G_i\) 相同的情况下，\(F_i\) 越大越好，这就不多解释了。
转移还要分类讨论一下。
\(a_i > i\) ：找到 \(1 \sim (a_i - i)\) 中最小的 \(G_j\) ，最大的 \(F_j\)
\(a_i \le i\) ：\(F_i = 1\) \(G_i = a_i\)
我们动态求前缀的最小的 \(G_j\) ，最大的 \(F_j\)。
#include<bits/stdc++.h>
#define int long long
#define debug(x) cout<<#x<<"[:]"<<x,puts("");
#define FOR(i,a,b) for(ll i=(a); i<=(b); ++i)
#define ROF(i,a,b) for(ll i=(a); i>=(b); --i)
//
//
//
using namespace std;
inline ll read() {
ll f = 0, t = 0;
char c = getchar();
while (!isdigit(c)) t |= (c == '-'), c = getchar();
while (isdigit(c)) f = (f << 3) + (f << 1) + c - 48, c = getchar();
return t ? -f : f;
}
void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
const int MX = 3e5 + 10;
int a[MX];
int f[MX], g[MX];
int ans[MX], G[MX];
sky pa[MX];
const int inf = 1e18 + 10;
struct sky {
int a,b,id;
};
sky merge(sky x,sky y) {
if(x.a < y.a) return x;
if(x.a > y.a) return y;
if(x.a == y.a)
if(x.b > y.b) return x;
else return y;
}
signed main() {
ios::sync_with_stdio(0), cout.tie(0);
int n = read();
int Q = read();
FOR(i,1,n) a[i] = read();
sort(a+1,a+n+1);
FOR(i,1,n) g[i] = inf;
FOR(i,1,n) {
if(i - a[i] >= 1) {
sky A = pa[i - a[i]];
f[i] = A.b + 1;
g[i] = A.a + A.id + a[i] + (i - a[i] - A.id);
} else f[i] = 1,g[i] = a[i];
sky B = {g[i] - i, f[i], i};
pa[i] = merge(B,pa[i - 1]);
}
FOR(i,1,n) G[i] = (n - g[i]) + f[i];
FOR(i,1,n) ans[G[i]] = i;
ROF(i,n,1) ans[i] = max(ans[i + 1],ans[i]);
FOR(i,1,Q) {
int k = read();
cout<<ans[k]<<" ";
}
return 0;
}
——end——
标签：个题,Marketi,int,CF1793E,sky,read,ans,Velepin,MX From： https://www.cnblogs.com/sirkey2119/p/18413877