bzoj4692: Beautiful Spacing

先二分答案后dp

设(su[n])为(sum_{1}^{n}xi[i])

设(f[n])为1时表示第n个单次能做某一行的结尾，且之前的空格满足二分出来的答案。

考虑怎样的(f[i])能转移至(f[n])：

1.(w - su[n] + su[i] >= n - i - 1)

2.((w - su[n] + su[i] - 1) / (n - i - 1) + 1 <= ans)

可以发现能转移的(f[i])是个区间，并且这个区间随(n)的增加单调递增。

于是我们可以维护(f)数组的前缀和，并用双指针维护这个区间即可。

复杂度(O(nlog(n)))

#include <bits/stdc++.h>
#define INF 10000000
#define N 100000
using namespace std;
int w, n;
int su[N], f[N];
deque <int> Q;
int main()
{
    while (scanf("%d%d", &w, &n), w + n)
    {
        for (int i = 1; i <= n; ++ i) scanf("%d", &su[i]), su[i] += su[i - 1];
        int ld = 1, rd = w;
        while (ld < rd)
        {
            int md = (ld + rd) / 2, ok = 0;
            for (int i = 1; i <= n; ++ i) f[i] = 0;
            f[0] = 1;
            for (int i = 2, l = 0, r = -1, sun = 0; i <= n; ++ i)
            {
                while (i - (r + 1) >= 2 && (w - su[i] + su[r + 1] - 1) / (i - (r + 1) - 1) + 1 <= md) sun += f[++ r];
                while (l <= r && w - su[i] + su[l] < i - l - 1) sun -= f[l ++];
                if (sun) f[i] = 1;
            }
            for (int i = 0; i <= n; ++ i)
                if (w - su[n] + su[i] >= n - i - 1 && f[i]) 
                    ok = 1;
            if (ok) rd = md; else ld = md + 1;
        }
        printf("%d
", ld);
    }
}