[CF803D] Magazine Ad（二分，贪心）

题目链接：http://codeforces.com/contest/803/problem/D

题意：字符串希望拆分成不大于k段，问如何拆分，使得每一行的字符串最短。其中有两个条件：空格或者连字符“-”允许换行。

二分每行最短的长度，检查的时候扫描i的字符串，固定两头，从右往左扫直到能换行，这样找到的是最长的满足每行长度<=二分到的值的长度。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int maxn = 1100100;
 6 int n, k;
 7 char s[maxn];
 8 
 9 bool ok(int p) {
10     int ret = 0;
11     for(int i = 0; i < n; ) {
12         ret++;
13         int r = i + p;
14         if(r >= n) break;
15         while(r > i && s[r-1] != ' ' && s[r-1] != '-') r--;
16         if(r == i) return 0;
17         i = r;
18     }
19     return ret <= k;
20 }
21 
22 int main() {
23     // freopen("in", "r", stdin);
24     // freopen("out", "w", stdout);
25     while(~scanf("%d",&k)) {
26         getchar();
27         gets(s);
28         n = strlen(s);
29         int ret = 0;
30         int l = 0, r = n;
31         while(l <= r) {
32             int mid = (l + r) >> 1;
33             if(ok(mid)) {
34                 r = mid - 1;
35                 ret = mid;
36             }
37             else l = mid + 1;
38         }
39         printf("%d
", ret);
40     }
41     return 0;
42 }