Description
排版是很有讲究的。假设稿纸的宽度是W个字符,长度不限,当你对一篇文章排版时,必须满足以下条件:
1.必须保持单词的次序。下图显示了对4个单词“This is a pen”在一张宽11字符的稿纸上排版的结果:
Input
输入的第一行是用空格分隔的两个正整数W和N(3<=W<=80000,2<=N<=50000),分别代表稿纸的宽度和单词数。接下来有N个正整数,第i个正整数xi代表第i个单词的长度(1<=xi<=(W-1)/2)。
Output
输出一个整数,代表最美观的排版中,最多出现多少个连续空格。
Sample Input
输入1:
11 4
4 2 1 3
输入2:
5 7
1 1 1 2 2 1 2
输入3:
11 7
3 1 3 1 3 3 4
输入4:
100 3
30 30 39
输入5:
30 3
2 5 3
Sample Output
输出1:
2
输出2:
1
输出3:
2
输出4:
40
输出5:
1
Data Constraint
2<=N<=50000
题解
这题十分的妙♂。
为什么呢?我们看到数据范围,发现没有部分分。
所以无脑乱打是不能准确估分的。
然鹅其实数据给水了,做法98分。血赚不亏。
98%
我们考虑DP。
设表示当且以第个字符为某行的结尾的最小最大空格。
转移我们再枚举一个来转移,利用前缀和来辅助转移。
这样就是的了,比较简单。
100%
我打死也不会告诉你把j的取值范围手动调小一点就能过
正解是可以把n调成200000的。
(不知道出题人的brain是怎么了)
我们看到最小最大,想到什么?二分of course。
那么我们考虑二分一个答案,然后判断答案是否合法。
状态还是但是其中记录的可以改成true或false表示当前以为某行结尾,是否满足答案。
然后,我们发现,由于我们枚举了答案,我们的枚举范围就可以得到了。
两个东东:
依照这两个玩意依次推进即可。
很像单调队列是吧~
随意转移。
标程
98%
uses math;
var
i,j,n:longint;
m,ans,zd,l,k:int64;
f,a,sum:array[0..50000] of int64;
begin
//assign(input,'spacing.in');reset(input);
readln(m,n);
for i:=1 to n do
begin
read(a[i]);
sum[i]:=sum[i-1]+a[i];
end;
fillchar(f,sizeof(f),127 div 3);
f[0]:=0;
zd:=f[1];
for i:=2 to n-1 do
begin
for j:=i-2 downto 0 do
begin
if j=1 then continue;
if (sum[i]-sum[j])+(i-j-1)>m then break;
k:=m-(sum[i]-sum[j]);
if k mod (i-j-1)>0 then l:=k div (i-j-1)+1
else l:=k div (i-j-1);
if (f[j]<>zd) and (f[j]>l) then l:=f[j];
if f[j]<>zd then
f[i]:=min(f[i],l);
end;
end;
ans:=1000*maxlongint;
for i:=n-1 downto 0 do
begin
if (sum[n]-sum[i])+(n-i-1)>m then break;
ans:=min(ans,f[i]);
end;
if ans=0 then ans:=1;
writeln(ans);
end.
100%
uses math;
var
i,j,n,r:longint;
m,ans,zd,l,k,st,en,mid,answer:int64;
a,sum:array[0..50000] of int64;
f:array[0..50000] of boolean;
function pd(mid:longint):boolean;
var
i,j,k,r,rr:longint;
begin
fillchar(f,sizeof(f),false);
f[0]:=true;
r:=0;
rr:=-maxlongint;
for i:=2 to n-1 do
begin
while (r<i) and (sum[i]-sum[r]+mid*(i-r-1)>=m) do
begin
if f[r]=true then
begin
rr:=r;
end;
inc(r);
end;
if (rr<>-maxlongint) and (sum[i]-sum[rr]+(i-rr-1)<=m) then
begin
f[i]:=true;
end
else f[i]:=false; {
while (sum[i]-sum[rr]+(i-rr-1) div 2)>=m do inc(rr);
while (sum[i]-sum[r])+(i-r-1)<=m do inc(r);
for j:=rr downto r do
begin
if (sum[i]-sum[j])+(i-j-1)>m then break;
if f[j]<>zd then
begin
k:=m-(sum[i]-sum[j]);
if k mod (i-j-1)>0 then l:=k div (i-j-1)+1
else l:=k div (i-j-1);
if (f[j]<>zd) and (f[j]>l) then l:=f[j];
if f[j]<>zd then
f[i]:=min(f[i],l);
end;
end; }
end;
ans:=1000*maxlongint;
for i:=n-1 downto 0 do
begin
if (sum[n]-sum[i])+(n-i-1)<=m then
begin
if f[i]=true then exit(true);
end;
end;
exit(false);
end;
begin
//assign(input,'spacing.in');reset(input);
readln(m,n);
for i:=1 to n do
begin
read(a[i]);
sum[i]:=sum[i-1]+a[i];
end;
st:=1;
en:=m;
answer:=1;
while st<=en do
begin
mid:=(st+en) div 2;
if pd(mid) then
begin
en:=mid-1;
answer:=mid;
end
else
begin
st:=mid+1;
end;
end;
writeln(answer);
end.
end.