Description
题目链接: https://codeforces.com/gym/101412
打训练赛时遇到的题目，感觉做法十分的优雅~
题意是给了 $n$ 个字符串，希望把它们有序地放进一个宽为 $w$ 的矩形方格中，相邻的两个字符串之间必须存在空格，除最后一行外，其余每行开头和末尾的格子都必须填有字符串，问字符串之间间隔的最大值最小能是多少？ $(3 \le w \le 80000, 2 \le n \le 50000)$
Solution
由题可知，这是一个最大值最小化的问题，我们容易想到用二分来处理这类问题.
尝试二分答案，假设字符串之间间隔的最大值是 $x$，我们利用动态规划的方法来进行字符串的填充.
记 $dp[i]$ 表示是否存在方案使得前 $i$ 个字符串已被填充，且字符串 $i$ 被填充在行末.
初始化 $dp[0]=1$，对于 $dp[i]$ 来说，字符串 $i$ 如果能填充在行末，它一定是从某个 $dp[j]$ 转移过来的$(其中dp[j]=1)$，然后字符串 $[j+1,i]$ 都填充在同一行.
若想将字符串 $[j+1,i]$ 都填充在同一行，需要满足(记 $sum[i]$ 为前 $i$ 个字符串的总长度):
$sum[i]-sum[j]+i-j-1 \le w \le sum[i]-sum[j]+x×(i-j-1)$
我们可以用当前的 $dp[i]$ 来更新后面的 $dp$ 值，如果 $dp[i]=1$， 我们知道 $sum[r]-sum[i]+r-i-1$ 随着 $r$ 的增大而增大，那么我们可以找到一个区间 $[i+1, r]$ 使得它们满足左边的不等式，同时我们判断区间内哪些点满足右边的不等式，更新这些点的 $dp$ 值为1.
对于 $r$ 来说，$i$ 越大，右边的不等式越不可能满足，因而如果 $r$ 被某一个 $i$ 判断过（即当左边的不等式成立），那么它就不需要 $j（j>i）$ 来进行判断了. 因此我们只需要用一个指针 $r$，让其从左往右扫，就可以更新出每一个点的 $dp$ 值了.
具体做法可以参考代码，感觉解法还是非常优雅的~
AC code
Time: 1310ms
Memory: 800KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iomanip>
using namespace std;
#define mem(a,i) memset(a,i,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&-x)
#define sqr(x) ((x)*(x))
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int maxn=5e4+5;
ll w;
int n;
ll a[maxn];
ll sum[maxn];
bool dp[maxn];
bool judge(ll x) {
rep(i,1,n) dp[i]=0;
dp[0]=1;
int r=0;
rep(i,0,n-1) {
if(dp[i]) {
if(r<i) r=i+1;
while(r<=n&&sum[r]-sum[i]+r-i-1<=w) {
if(sum[r]-sum[i]+x*(r-i-1)>=w) {
dp[r]=1;
}
++r;
}
if(r>n) return true;
}
}
return false;
}
int main() {
while(~scanf("%lld%d",&w,&n)) {
if(w==0&&n==0) break;
rep(i,1,n) scanf("%lld",&a[i]);
sum[0]=0;
rep(i,1,n) sum[i]=sum[i-1]+a[i];
ll l=1,r=w;
ll ans;
while(l<=r) {
ll mid=(l+r)>>1;
if(judge(mid)) {
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%lld\n",ans);
}
return 0;
}