JZOJ 3242. Spacing
\(\text{Analysis}\)
最大值最小很容易想到二分答案
然后用 \(dp\) 检查
设 \(f_i\) 表示当前行最后一个为 \(i\) 时最优情况最大空格数是否小于 \(mid\)
若 \(f_i = 1\) 可行
则存在一个 \(j\),令 \(j\) 为当前行开头
使得 \(f_{j-1} = 1\) 且 \(sum_i-sum_{j-1}+i-j \le w\) 且 \(sum_i - sum_{j-1}+mid \cdot (i-j) \ge w\)
第一条表示 \(j\) 之前最大空格数小于 \(mid\)
第二条表示 \(j\) 到 \(i\) 之间至少一个空格时能填入当前行
第三条表示 \(j\) 到 \(i\) 之间空格数都为 \(mid\) 时大于等于当前行
第三条能保证当前行最长空格数小于等于 \(mid\)
那么我们只要判断是否存在这样的 \(j(j \le i)\) 即可
观察第三条式子,发现满足第三条式子时 \(j\) 是连续的
再看第二条式子,在 \(j\) 满足第三条时 \(j\) 越大越容易满足
那么我们记录最优决策即可
\(i\) 变大后可以发现这个最优决策一定不早于上一个最优决策
\(\text{Code}\)
#include
#include
#include
using namespace std;
const int N = 5e4 + 5;
int w, n, a[N], sum[N], f[N];
inline int check(int mid)
{
int p = 1, q = -1;
f[0] = 1;
for(int i = 1; i <= n; i++) f[i] = 0;
for(int i = 1; i <= n; i++)
{
while (p <= i && sum[i] - sum[p - 1] + mid * (i - p) >= w)
{
if (f[p - 1]) q = p;
++p;
}
f[i] = (q != -1 && sum[i] - sum[q - 1] + i - q <= w);
}
for(int i = n; i; i--)
if (f[i - 1] && sum[n] - sum[i - 1] + n - i <= w) return 1;
return 0;
}
int main()
{
scanf("%d%d", &w, &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
int ans, l = 1, r = w - 2, mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n", ans);
}