Magazine Ad
题目链接：http://codeforces.com/contest/803/problem/D
——每天在线，欢迎留言谈论。
题目大意：
给你一个数字k，和一行字符 例：
garage for sa-le
其中这行字符串能够在 ' '与'-'的后面分割。例如分割为：(点代表空格)
garage.
for.
sa-
le
求：分割成不超过k行的情况下的最小宽度。(宽度：最大行的字符个数)
思路：
答案一定在 到 所给字符串长度 之间。
①通过二分宽度 来逼近最小宽度。
判断每行宽度<=m 并在k行内完成分割时
②贪心地把每行填的不能再填为止。
AC代码：
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
string ss;
int n;
bool isok(int k)//是否能在k宽度下满足条件
{
int a(),b1(),b2();//a行数 b 宽度
for(int i=;i<ss.size();i++)
{
if(i!=ss.size()-)
b2++;
if(ss[i]==' '||ss[i]=='-')
{
if(b2>k)
return false;
if(b1+b2<=k)
{
b1=b1+b2;b2=; }
else
{
b1=b2;b2=;a++;
if(a>n)
return false;
}
}
}
if(a>n)
return false;
return true;
}
int main()
{
cin>>n;getchar();
getline(cin,ss);
ss+=' ';
int i=,j=ss.size(),k;//[i,j)
while(i<j)
{
k=(i+j)/;
if(isok(k))
j=k;
else
i=k+;
}
if(i==ss.size()&&isok(i))
{cout<<i<<endl;return ;}
cout<<i<<endl;return ;
}
2017-05-06 22:03:30