首页 > 代码库 > 【BZOJ-4692】Beautiful Spacing 二分答案 + 乱搞（DP？）

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

2024-08-12 19:10:38   220人阅读

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列的网格正确和错误的例子。
技术分享
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=0; char ch=getchar();    while (ch<‘0‘ || ch>‘9‘) {ch=getchar();}    while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}    return x;}#define MAXN 100010int W,N,sum[MAXN];bool f[MAXN];inline bool check(int x){    int l,r,t; l=r=t=0;    for (int i=2; i<=N; i++)        {            while (i-r>=2 && (W-(sum[i]-sum[r]))<=x*(i-r-1)) t+=f[r++];            while (l<=r && W-(sum[i]-sum[l])<i-l-1) t-=f[l++];            if (t) f[i]=1; else f[i]=0;        }    for (int i=0; i<=N; i++) if (f[i] && W-(sum[N]-sum[i])>=N-i-1)        return 1;    return 0;}int main(){    f[0]=1;    int l,r,mid;    while (W=read(),N=read())        {            if (!W && !N) break;            for (int i=1; i<=N; i++) sum[i]=sum[i-1]+read();            l=1,r=W;            while (l<=r)                {                    mid=(l+r)>>1;                    if (!check(mid)) l=mid+1; else r=mid-1;                 }            printf("%d\n",l);        }    return 0;}

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

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


联系
我们