题目描述
奶牛 Bessie 正在完成她的写作课的一篇作文。
这篇作文共有 N 个单词,用空格分隔。
每个单词的长度在 1 到 15 之间,仅由大写和小写字母组成。
根据作业的要求,这篇作文需要用一种特别的方式排版:
每一行包含的字符不超过 K 个,空格不计。
幸好 Bessie 的单词处理器能够处理这样的要求,它会按照如下的方式:
如果 Bessie 输入了一个单词,这个单词能够放进当前行,就放在当前行。
否则,将这个单词放到下一行,然后继续向下一行添加单词。
当然,同一行中的单词之间仍然用一个空格分隔。每一行的结尾都不应当有空格。
思路
记录每个单词的个数,然后根据当前行所用单词字数 + 当前单词字数 是否超过K
超过则将当前单词输出到下一行
没有的话则将单词输入到当前行
有点疑惑的是每一行的结尾都不应当有空格,不处理一样能AC,对于如何处理这个也没有好的思路==
算法1
(暴力枚举) $O(n^2)$
blablabla
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
char str[N][20]; //存取单词
int n,k;
int len[N]; //获取每个单词的长度
int main()
{
cin>>n>>k;
int res=0;
//存取单词且同时记录单词的长度
for(int i=1;i<=n;i++)
{
cin>>str[i];
len[i] = strlen(str[i]);
}
//枚举
for(int i=1;i<=n;i++)
{
if(res+len[i]<=k) //当前行的单词个数 + 下一个单词个数是否小于等于K,在当前行输出
{
cout<<str[i]<<" ";
res = res + len[i]; //记录当前行的单词个数
}
else //否则,换行输出
{
puts("");
cout<<str[i]<<" ";
res = len[i];
}
}
}
算法2
不需要开多维数组存取长度和单词,直接输入的时候进行处理
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
char str[20];
int n,k;
int len;
int main()
{
int res=0;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>str;
len = strlen(str);
if(res+len<=k)
{
cout<<str<<" ";
res += len;
}
else
{
puts("");
cout<<str<<" ";
res = len;
}
}
}