Velepin and Marketing 题解
zmx_wzx_JY
·
·
题解
闲话
如果我的 CF rating 是 2099，我将完成绝杀，可惜我不是
所以原题场 rated 真的好吗
不过 E 还是挺有意思的，所以写一下题解。
题意
有 n 个人，每个人有一个值 a_i，要将 n 个人划分成 k 组，每个人会被满足当且仅当他所在的组人数不小于 a_i。
多次询问，每次给定 k，问最多满足多少个人。
## 题解
首先将 $a_i$ 从小到大排序，然后分析一些简单的性质：
1. 最优情况下被满足的人一定是个前缀。
证明显然。
2. 答案随 $k$ 增大单调不增。
证明：合并两组不会让答案变少。
3. 最优情况下，每组的人是连续的一段。
证明：否则交换顺序错了的一对肯定更优。
然后之后大概会去猜一个结论，每个组内如果有被满足的人，则该组所有人都被满足。
很遗憾这个结论是错的（据说直接按这个假结论写会 WA on pretest 6)，不过我们把这个结论修正一下就对了：
我们认为一个组是“有效”的，当且仅当组内有被满足的人。则如果有效的组不止一个，则所有有效的组内的人全部被满足。
证明：如果有多于一个有效的组，且存在一个有效的组内人没有全部被满足。则可以把这个组内一个不满足的人留在这个组，其余人加入另一个有效的组，则答案不会变劣。
于是我们分别处理两种情况：
1. 只有一个有效的组
最优方案显然是后 $k-1$ 个人一人一组，前面 $n-k+1$ 个人一组。记 $cnt_i$ 表示 $a$ 值不超过 $i$ 的人数，则这部分答案显然是 $min(n-k+1,cnt_{n-k+1})$。
2. 每个有效组内的人全部满足
容易想到一个 $dp$，$f_i$ 表示保证前 $i$ 个数都合法的情况下，前 $i$ 个数最多能划分成几段。
转移的话显然是用 $f_i= \operatorname{max}_{leq j\leq i-a_i}f_j+1$，显然 dp 的时候同时维护 $f$ 的前缀最大值快速转移。
dp 完了后用 $i$ 去$\operatorname{chkmax}$ $ans_{[1,f_i+n-i]}$ 即可。
两种情况取 max 即可。
总复杂度 $O(n)$。
## code
```cpp
#include<bits/stdc++.h>
#define Rep(i, x, y) for(int i = (x), stOyny = (y); i <= stOyny; ++i)
#define Irep(i, x, y) for(int i = (x), stOyny = (y); i >= stOyny; --i)
using namespace std;
template<typename T>
inline void tmax(T &x, const T y) { if(x < y) x = y; }
const int N = 3e5 + 20;
int n, a[N], f[N], g[N], ans[N], cnt[N];
signed main() {
// freopen("1.in", "r", stdin);
ios::sync_with_stdio(false);
cin >> n;
Rep(i, 1, n) cin >> a[i], cnt[a[i]]++;
Rep(i, 1, n) cnt[i] += cnt[i - 1];
sort(a + 1, a + n + 1);
Rep(i, 1, n) {
if(a[i] <= i) tmax(ans[(f[i] = g[i - a[i]] + 1) + n - i], i);
g[i] = max(g[i - 1], f[i]);
}
Irep(i, n, 1) tmax(ans[i], ans[i + 1]);
int T;
cin >> T;
while(T--) {
int x;
cin >> x;
cout << max(ans[x], min(n - x + 1, cnt[n - x + 1])) << '\n';
}
return 0;
}
```
## 总结
一道不错的找性质题，直接猜结论的话比较容易假，循序渐进地推结论可以比较顺利地做出来。