Magazine Ad CodeForces - 803D（二分 + 貪心，第一次寫博客）

Magazine Ad

The main city magazine offers its readers an opportunity to publish their ads. The format of the ad should be like this:

There are space-separated non-empty words of lowercase and uppercase Latin letters.

There are hyphen characters '-' in some words, their positions set word wrapping points. Word can include more than one hyphen.

It is guaranteed that there are no adjacent spaces and no adjacent hyphens. No hyphen is adjacent to space. There are no spaces and no hyphens before the first word and after the last word.

When the word is wrapped, the part of the word before hyphen and the hyphen itself stay on current line and the next part of the word is put on the next line. You can also put line break between two words, in that case the space stays on current line. Check notes for better understanding.

The ad can occupy no more that k lines and should have minimal width. The width of the ad is the maximal length of string (letters, spaces and hyphens are counted) in it.

You should write a program that will find minimal width of the ad.

Input

The first line contains number k (1 ≤ k ≤ 10⁵).

The second line contains the text of the ad — non-empty space-separated words of lowercase and uppercase Latin letters and hyphens. Total length of the ad don't exceed 10⁶ characters.

Output

Output minimal width of the ad.

Examples

4
garage for sa-le

7

4
Edu-ca-tion-al Ro-unds are so fun

10

Note

Here all spaces are replaced with dots.

In the first example one of possible results after all word wraps looks like this:

garage.
for.
sa-
le

The second example:

Edu-ca-
tion-al.
Ro-unds.
are.so.fun

題目大意：有一組字元串，用連字元‘-’以及空格‘ ’進行分割，要求分割不超過k段，求分割後的最小寬度（寬度就是分割後最長的字元串的長度）。
思路：博主是個菜雞，一開始沒啥思路，學姐講題的時候才想到用二分。。。。。。。。
　　經過不斷地啃博客（正經臉），算是明白一點如何從 二分 入手這道題。
　　把每一段字元串 按照一個長度 x 進行分割，得到的字元串長度不能超過 x ，看最後得到的行數是否小於k；
　　如果按長度x進行分割得到的行數小於k 那麼按長度 x+1 進行分割所得到的行數必定小於k。
　　註意 最小寬度 定義，這個時候我們就可以用二分，不斷地去逼近這個最小寬度，就可以得到答案。
　　最後註意的就是二分的上下界，上界就是初始字元串的長度s.size(),下界可以是s.size()/k（這個博主就不解釋了）。
AC代碼：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 vector<int>v;
 4 string s;
 5 int k;
 6 bool check(int x){
 7     int line = 0;// 記錄以x切割時可以得到的行數     
 8     int len = 0; 
 9     for(int i = 0 ;  i < v.size();  i++){
10         if(v[i] > x){
11             return 0;// 如果v[i] > x 說明存在v[i]讓x無法表示（說明x取小了） 
12         }
13         if(v[i] + len > x){
14             line++;
15             len = v[i];
16         }else if(v[i] + len == x){
17             line++;
18             len = 0;
19         }else if(v[i] + len < x){
20             len += v[i];
21         }// 將字元串 以不大於x 的長度分割
22         // line 記錄進行分割後得到的總行數 
23     }
24     if(len > 0) line++;// 註意分割最後的一小段字元串是否忽略 
25     return line <= k;// 根據x分割所得到的總行數不能大於k 
26 }
27 
28 int main(){
29     while(~scanf("%d",&k)){
30         v.clear();
31         getchar();
32         getline(cin,s);
33         int j = 0;
34         for(int i = 0 ; i < s.size(); i++){
35             if(s[i] == ' ' || s[i] == '-'){
36                 v.push_back(j + 1);
37                 j = 0;
38             }else j++;
39         }
40         v.push_back(j);// 不要忘記末尾的字元串長度 
41         int l = s.size()/k, r = s.size();
42         while(r - l > 0){
43             int mid = (r + l)/ 2;
44             if(check(mid)){
45                 r = mid;
46             }else{
47                 l = mid + 1;
48             }
49         }
50         printf("%d\n",l);
51     }
52     return 0;
53 }

一個從很久以前就在做的夢。