题解 CF958E2 【Guard Duty (medium)】

另一个老哥是真莽，$nk=5\cdot 10^5*5\cdot 10^3=2.5e9$ 这都能 `2995ms` 给爆过去，orzorz 发现题解区好像没有正常复杂度的，于是这里给出一个正常一点的带权二分做法。 _____ 考虑一般 $dp$ 的话就是 $f_{i,j}$ ，这个地方由于不限制一定要取满，所以就可以有如下转移： $$ f_{i,j}=\min\{f_{i-1,j},f_{i-2,j-1}+len(i-1,i)\} $$ 似乎常数小一点，暴力 $O(nk)$ 也是可以过的。于是就直接wqs二分一下，注意到由于此时最优的决策一定是少选，所以每选一次就需要减去 $mid$ 来维护这个限制。于是最后复杂度 $n\log V$ 。 需要注意的是，由于用了 $cnt_i$ 记录转移到 $i$ 这个状态至少要分成多少段，所以这个地方还是牵扯到一个，如果我可以有 $6/7/8$ 三种划分方式转移到最优解，那么到底应该用哪个。很显然的是要么用 $max$ 要么用 $min$，这取决于二分的方式。如果是取 $max$ 的话，那么可能 $cnt_n>m$ ；取 $min$ 的话则会 $\leq m$ 。所以根据这个调整代码细节就好了。 ```cpp ll res ; ll f[N] ; int m, n ; int df[N] ; int cnt[N] ; int base[N] ; bool check(int x){ x *= -1 ; for (int i = 2 ; i <= n ; ++ i){ if (f[i - 1] < f[i - 2] + df[i] + x) f[i] = f[i - 1], cnt[i] = cnt[i - 1] ; else f[i] = f[i - 2] + (ll)df[i] + (ll)x, cnt[i] = cnt[i - 2] + 1 ; if (f[i - 1] == f[i - 2] + df[i] + x) cnt[i] = max(cnt[i - 1], cnt[i - 2] + 1) ; } res = f[n] - (ll)x * m ; return (bool)(cnt[n] >= m) ; } int main(){ cin >> m >> n ; for (int i = 1 ; i <= n ; ++ i) scanf("%d", &base[i]) ; sort(base + 1, base + n + 1) ; for (int i = 1 ; i <= n ; ++ i) df[i] = base[i] - base[i - 1] ; int l = 0, r = 1e9, mid, ans ; while (l <= r){ mid = (l + r) >> 1 ; // cout << l << " " << r << endl ; if (check(mid)) ans = mid, r = mid - 1 ; else l = mid + 1 ; } check(ans) ; cout << res << endl ; return 0 ; } ```