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

发布于 2019-08-13  186 次阅读


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<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
const int maxn = 1005;
typedef long long ll;

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;
}

愿风指引你的道路,愿你的刀刃永远锋利。