[牛客暑期多校第七场][暴力+贪心]A-String

https://ac.nowcoder.com/acm/contest/887/A

题意：给定一个字符串 把他分割成最小字符串组成的多个串 数量要求最少
最小字符串：通过旋转（第一个字符到最后面去）得到最小的字符串
比如011 最小是011
010 最小是001
0101 最小是0101
注意这个题 是求最少的分割数量 比赛的时候卡住了 比赛结束3分钟就AC了。。。
其实可以贪心 直接暴力最长的串是不是最小 不是的话ed–（st初始为0 ed初始为s的长度-1） 一直减 直到遇到那个最长的最小字符串 然后更新st为ed+1 ed初始化
以此往复 直到输出全部字符串

#include
#include
#include
#include
#include
#include
#include
#include
#include

bool judge(string a) {
if (a.length() == 1) return true;
int len = a.length();
string ans = a;
string b = a;
for (int i = 0; i < a.length(); i++) {
char c = a[len - 1];
a.erase(a.end() - 1);
a = c + a;
ans = min(ans, a);
}
if (ans == b)
return true;
else
return false;
}

int main() {
int t;
cin >> t;
string s;
int st, ed;
while (t–) {
cin >> s;
int st = 0, ed = s.length()-1;
while (st <= ed) {
if (judge(s.substr(st, ed - st+1)) == true) {
cout << s.substr(st, ed - st+1)<<’ ‘;
st = ed + 1;
ed = s.length() - 1;
}
else {
ed–;
}
}
cout << endl;
}
return 0;
}