CF803D Solution

题目链接

题解

\(O(nlogn)\)的数据范围与求最大值最小的条件，可以想到二分答案。\(check\)函数只需扫一遍字符串，如果当前行到换行点的长度\(>mid\)的话，则采用上一个换行点。换言之就是采用每个使该行长度\(\le mid\)且最大的换行点，如果最后行数\(>k\)则返回\(false\)。

Tips：输入的字符串含有空格，无法使用\(scanf\)或\(cin\)，需要用\(getline\)（string）或\(gets\)（char数组）。但如果直接在输入\(k\)后使用，其读入的是该行剩下的部分也就是一个换行符，因此需要先使用\(getchar\)（\(cin\)和\(scanf\)无法读入换行和空格）将换行符读入再\(getline\)或\(gets\)。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string a;
int k,n,len[N],cnt;//len[i]:第i个与第i-1个换行点之间的长度(含第i个)
bool check(int mid)
{
	int qwq=0,sum=1;//qwq:当前行的长度,sum:当前行数(行数=换行点数+1,因此sum=1)
	for(int i=1;i<=cnt;i++)
	{
		if(mid<len[i]) return 0;
		qwq+=len[i];
		if(qwq>mid)
		{
			qwq=len[i],sum++;
			if(sum>k) return 0;
		}
	}
	return 1;
}
int main()
{
	scanf("%d",&k); char in=getchar(); 
	getline(cin,a); n=a.size();
	int pos=-1; 
	for(int i=0;i<n;i++)
		if(a[i]=='-' || a[i]==' ') len[++cnt]=i-pos,pos=i;
	len[++cnt]=n-1-pos; //最后一个换行点后的部分
	int l=1,r=n,ans;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d",ans);
	return 0;
}