尝试二分答案,问题变为要求恰好选 \(x\) 段 \(\ge s\),最大化选的段数。
发现我们不是很会算段数的 \(\max\),因为要求段不重不漏地覆盖 \([1, n]\)。考虑给每个 \(\ge s\) 段 \([l, r]\) 一个 \(r - l\) 的代价,于是变成了算代价的 \(\min\)。此时不再要求段不重不漏地覆盖,因为我们可以把没被覆盖的部分接到旁边的 \(\ge s\) 段。
设 \(f(x)\) 为选出恰好 \(x\) 个 \(\ge s\) 的段,每一段 \([l, r]\) 的代价定义为 \(r - l\),代价的 \(\min\)。那么一个答案 \(x\) 合法当且仅当 \(f(x) \le n - k\)。
发现 \(f(x)\) 下凸(感性理解就是选的段的代价会越来越大),那么 \((x, f(x))\) 构成一个下凸包的右半边(即斜率 \(> 0\) 的部分)。套路地 wqs 二分斜率 \(k\),选一段的代价变成 \(r - l - k\),在此基础上求选出若干段的代价 \(\min\) 和在取到这个 \(\min\) 的前提下至少选了多少段即可。
上面那个问题显然可以 dp 求出。dp 数组单调,所以只用考虑最近的一个合法转移点转移过来(即对于每个 \(i\) 满足 \(\sum\limits_{k = j}^i a_k \ge s\) 的最小的 \(j\))即可。
预处理每个位置的最近合法转移点,总时间复杂度 \(O(n \log^2 n)\)。
code
// Problem: E - Subsegments with Large Sums
// Contest: AtCoder - ALGO ARTIS Programming Contest 2023 Autumn(AtCoder Regular Contest 168)
// URL: https://atcoder.jp/contests/arc168/tasks/arc168_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 250100;
ll n, m, K, a[maxn], b[maxn], p[maxn];
pii f[maxn];
inline pii solve(ll x) {
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1];
if (p[i]) {
f[i] = min(f[i], mkp(f[p[i] - 1].fst + i - p[i] - x, f[p[i] - 1].scd + 1));
}
}
return f[n];
}
inline bool check(ll x) {
ll l = 0, r = n, pos = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (solve(mid).scd <= x) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return solve(pos).fst + x * pos <= n - K;
}
void solve() {
scanf("%lld%lld%lld", &n, &K, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
b[i] = b[i - 1] + a[i];
}
for (int i = 1, j = 0; i <= n; ++i) {
while (b[i] - b[j] >= m) {
++j;
}
p[i] = j;
}
ll l = 0, r = K, ans = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Subsegments AtCoder Regular Contest Largesubsegments atcoder regular contest atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest builder atcoder regular contest 164 disconnected atcoder regular contest