D. Magazine Ad
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 ≤ 105).
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 106 characters.
Output
Output minimal width of the ad.
Examples
inputCopy
4
garage for sa-le
outputCopy
7
inputCopy
4
Edu-ca-tion-al Ro-unds are so fun
outputCopy
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和一个字符串s，最多可以把s分成k行，分割位置只能是-或者空格，求分割后最长一行长度的最小值
题解：二分最后一行的长度的最小值，每次二分的时候检查一遍，每次检查的时候从0扫到最后即可
代码如下：
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int k,n; string str; int C(int w){ int ans=0; int l=0; //从左到右扫 while(l<n){ ans++; //最右端 int r=l+w; //最右段过了长度，找到一个大的了 就break返回答案了 r=mid 继续找更小的 if(r>=n) break; //如果没有到这个分段的边界 就-- while(r>l&&str[r-1]!='-'&&str[r-1]!=' ') r--; //如果减到这个分段的边界了，就证明二分到的这个答案小了 l=mid if(r==l) return INF; l=r; } return ans; } int main(){ cin>>k; getchar(); getline(cin,str); n=str.length(); int l=0,r=n; //二分答案找小长度 while(r-l>1){ int mid=(l+r)/2; if(C(mid)<=k) r=mid; else l=mid; } cout<<r<<endl; }