bzoj4692: Beautiful Spacing

时间：2024-10-10 00:02:57

先二分答案后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 = ; i <= n; ++ i) scanf("%d", &su[i]), su[i] += su[i - ];

        int ld = , rd = w;

        while (ld < rd)

        {

            int md = (ld + rd) / , ok = ;

            for (int i = ; i <= n; ++ i) f[i] = ;

            f[] = ;

            for (int i = , l = , r = -, sun = ; i <= n; ++ i)

            {

                while (i - (r + ) >=  && (w - su[i] + su[r + ] - ) / (i - (r + ) - ) +  <= md) sun += f[++ r];

                while (l <= r && w - su[i] + su[l] < i - l - ) sun -= f[l ++];

                if (sun) f[i] = ;

            }

            for (int i = ; i <= n; ++ i)

                if (w - su[n] + su[i] >= n - i -  && f[i])

                    ok = ;

            if (ok) rd = md; else ld = md + ;

        }

        printf("%d\n", ld);

    }

}

相关文章