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);
}