题意：
要求给一片文章排版，要求每行 $W$ 个格子，每一行的要求是首单词必须顶格，除了最后一行之外的尾单词也必须顶格，然后单词之间至少有 $1$ 个空格，单词内部不能有空格，也不能改变单词之间的顺序。现在问在排版方案满足这些要求的条件下，单词之间的最大空格最小是多少。数据量: 每一行的格子数： $3\le W \le 80,000$， 总共的单词数：$2\le N\le 50,000$ 每个单词的长度 $x_i$ 满足 $1\le x_i \le \frac{W-1}{2}$
题解：
非常好的DP题。话说我是不是这种二分然后dp check的遇到一道不会一道emmmm
我以前做的这种二分然后check的题目，很多都是把check的对象转换成一个数量，然后用dp在约束条件下得到一个最优化的解去跟某个数值相比对？这个题妙的一点是他直接dp的状态就是可行性，用s[i]表示第i个单词是否可以作为结尾。那么怎么转移呢？假设可以作为某一行的结尾，那么一定有一个单词作为开头与之对应，如果这不是第一行，那么就一定有这个开头的单词的前一个单词作为上一行的结尾与之对应，所以我们的问题变成了在约束条件下有没有一个可以作为开头的单词的前一个单词可以作为结尾，如果有至少一个这样的点那么这个单词 i 就也可以作为结尾，如果没有就不行。考虑到我们二分的上限和单词之间空格数至少为1的下限，我们可以很容易的得出来两个判断条件 slen[i]-slen[j-1]+i-j<=W， 和 slen[i]-slen[j-1]+(i-j)*wt>=W; ，其中slen是单词长度的前缀和。写出来数学公式之后我们就会发现这个东西对于j是单调的，那么就又可以用二分来查找边界了，换句话说可行的范围一定是一个连续的区间，我们二分找出边界找出两个边界 [l,r] 然后判断 [l-1,r-1] 之间是否有s[j]==1就行了。区间查询1的个数又可以用前缀和来判断，所以我们干脆把s[i]直接做成前缀和，这样每次只要查询 s[r-1]-s[l-2] 是否大于0就可以了。
最后一步的话，需要再次二分找出来可以作为最后一行开头的所有点，然后查他们前面的单词是否可以作为结尾就可以了。。。
wa点：
- 首先发现了我原来的二分写法解决不了解根本不在
[l,r]之间的这种情况。。需要用新的写法。 - 其次是忘记了差分前缀要考虑边界情况
- 最后是忘记了每个单词的长度上界并不是代表空格的长度上界。。搞错了
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
int W,N;
int slen[maxn],s[maxn];
inline bool ok1(int i,int j){return slen[i]-slen[j-1]+i-j<=W;}
inline bool ok2(int i,int j,int wt){return slen[i]-slen[j-1]+(i-j)*wt>=W;}
inline bool ok3(int j){return slen[N]-slen[j-1]+(N-j)<=W;}
bool check(int wt){
int L,R,FL,l,r,mid;
s[1]=s[0]=1;//0 can be the end
for(int i=2;i<=N;++i){
s[i]=s[i-1];
l=1,r=i;L=i+1,R=0;
while(l<=r){
mid=(l+r)>>1;
if(ok1(i,mid)) r=mid-1,L=mid;//error3
else l=mid+1;
}
//L=r;//error2 not found in the [l,r]
l=1,r=i;
while(l<=r){
mid=(l+r+1)>>1;
if(ok2(i,mid,wt)) l=mid+1,R=mid;
else r=mid-1;
}
//R=l;
s[i]+=(L<=R&&(L==1||s[R-1]-s[L-2]));//error1
}
l=1,r=N;
while(l<r){
mid=(l+r)>>1;
if(ok3(mid)) r=mid;
else l=mid+1;
}
return r==1||s[N-1]>s[r-2];//error1 diff
}
int main()
{
// freopen("test_.in","r",stdin);
// freopen("2.txt","w",stdout);
while(scanf("%d%d",&W,&N)==2&&W){
for(int i=1;i<=N;++i){
scanf("%d",&slen[i]);
slen[i]+=slen[i-1];
}
int l=1,r=W-2,mid;//error4 final error
while(l<r){
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",r);
}
return 0;
}