题目链接
http://codeforces.com/contest/803/problem/D
题意
字符串分成最大k行，使最大的那一行长度尽量小。 划分要求：空格或者-
思路
二分 二分一下每行最大多长，然后判断即可。
代码
#include <bits/stdc++.h>
using namespace std;
inline int in() {
int x;
scanf(
"%d", &x);
return x;}
#define pr(x) {cout << #x << ' ' << x << endl;}
const int maxn =
1e6 +
5;
vector<int> v;
int k, n;
char a[maxn];
bool judge(
int len) {
if (v.empty())
return n <= len ?
1 :
0;
int cnt =
0, tot =
1;
for (
int i =
0; i < v.size(); i++) {
int x = v[i];
if (x > len)
return false;
if (cnt + x <= len) {
cnt += x;
}
else {
++tot;
cnt = x;
}
}
return tot <= k;
}
int main() {
k = in();
getchar();
cin.getline(a, maxn -
1);
n =
strlen(a);
vector<int> tmp;
for (
int i =
0; i < n; i++) {
if (a[i] ==
' ' || a[i] ==
'-')
tmp.push_back(i);
}
for (
int i =
0; i < tmp.size(); i++) {
v.push_back(tmp[i] - (i ? tmp[i -
1] : -
1));
}
if (tmp.size()) v.push_back(n - tmp.back() -
1);
int l =
0, r = n, m, ans = n;
while (l <= r) {
m = l + (r - l >>
1);
if (judge(m)) r = m -
1, ans = m;
else l = m +
1;
}
cout << ans << endl;
return 0;
}
