【BZOJ-4692】Beautiful Spacing 二分答案 + 乱搞（DP？）

2023-07-31 15:41:28

4692: Beautiful Spacing

Time Limit: 15 Sec Memory Limit: 128 MB
Submit: 46 Solved: 21
[Submit][Status][Discuss]

Description

文章是一些单词组成的序列，单词由字母组成。你的任务是将一篇文章的单词填充到一个网格中，其中网格包含W列和足够多的行。为了布局之美，以下限制都需要满足。

1.文章中的文字需要按照原有的顺序放置。下图表示了将4个单词的文章“This is a pen”放入11列的网格正确和错误的例子。

【BZOJ-4692】Beautiful Spacing 二分答案 + 乱搞（DP？）

2.在同一行的两个相邻单词之间要有至少一个空格。有时你会需要放置多于一个空格来满足其他限制。

3.一个单词必须被放置到连续的列中，一个格子只含一个字符。你不能将通过增加空格或换行将一个单词分成多个部分。

4.文章必须占据边缘两列的格子，即每行的第一个单词必须占用第一个格子，且除了最后一行之外的每行的最后一个单词必须占用最后一个格子。

文章拥有最美的布局时，每一行都不会有过多的连续空格，在下图的例子里只有最多2个连续空格，而第一个例子里有3个连续空格，所以下图的例子比第一个例子美观。给定文章的信息和列数，请你找到一个最优的布局，使得最长连续空格尽量短。

Input

输入包含多组测试数据。每组数据第一行包含两个正整数W和N，其中W表示列数(3≤W≤80000)，N表示文章的单词数量(2≤N≤50000)。

第二行包含N个正整数，按照文章中单词的顺序给出每个单词的字符数量，对于第i个单词的字符数量xi，有1≤x_i≤(W-1)/2，从而这也使得答案一定存在。

输入以两个零作为结束。

Output

对于每组数据，输出一个正整数表示最长连续空格长度的最小值。

Sample Input

11 4
4 2 1 3
5 7
1 1 1 2 2 1 2
11 7
3 1 3 1 3 3 4
100 3
30 30 39
30 3
2 5 3
0 0

Sample Output

2
1
2
40
1

HINT

Source

鸣谢Tangjz提供试题

Solution

二分+乱搞

首先,要求间隔最大的最小,显然可以二分答案.然后判定;

得到最大的间隔x后,我们可以得到用每个单词为一行结尾时的之前的可行范围

然后我们考虑通过之前的答案转移过来，

满足能放开[l,r]（算上中间的空格），以及空格<=x，这样我们用两个指针l,r来找即可

我也不知道这种方法算是什么？模拟？

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

inline int read()

{

    int x=; char ch=getchar();

    while (ch<'' || ch>'') {ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x;

}

#define MAXN 100010

int W,N,sum[MAXN];

bool f[MAXN];

inline bool check(int x)

{

    int l,r,t; l=r=t=;

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

        {

            while (i-r>= && (W-(sum[i]-sum[r]))<=x*(i-r-)) t+=f[r++];

            while (l<=r && W-(sum[i]-sum[l])<i-l-) t-=f[l++];

            if (t) f[i]=; else f[i]=;

        }

    for (int i=; i<=N; i++) if (f[i] && W-(sum[N]-sum[i])>=N-i-)

        return ;

    return ;

}

int main()

{

    f[]=;

    int l,r,mid;

    while (W=read(),N=read())

        {

            if (!W && !N) break;

            for (int i=; i<=N; i++) sum[i]=sum[i-]+read();

            l=,r=W;

            while (l<=r)

                {

                    mid=(l+r)>>;

                    if (!check(mid)) l=mid+; else r=mid-;

                }

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

        }

    return ;

}

压了半天常，结果还是输rank1 100ms.....不甘心....

码农公寓