JZOJ 3242. Spacing

( ext{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) 变大后可以发现这个最优决策一定不早于上一个最优决策

( ext{Code})

#include<cstdio>
#include<iostream>
#include<cstring>
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
", ans);
}