欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 1584 - Circular Sequence(模拟)

程序员文章站 2022-06-09 20:18:50
...

UVA 1584 - Circular Sequence(模拟)UVA 1584 - Circular Sequence(模拟)

题目大意:

输入一个n表示有n组数据,接下来输出n个字符串,要求输出这个字符串字典序最小的那一个,注意是环状,比如1234 几个字符串就是 1234 2341 3412 4123 。

解题思路:

模拟这几个环状即可,O(n)的去枚举每一个序列,维护一个最小值即可。这里我用string类去存,这里我用到了一个函数:substr()字符串截取函数,对于每一个 i 当前的环状序列是(第i个字符到末尾字符)+(第1个字符到第i-1个字符) 一个一个去比较即可。AC代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int _max = 1e3+50;
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		string s,ans;
		cin>>s;
		ans=s;
		for(int i=0;i<s.length();i++)
		{
			string t="";
			t+=s.substr(i)+s.substr(0,i);//枚举每一个序列
			ans=min(ans,t);//维护字典序最小
		}
		cout<<ans<<endl;
	}
	return 0;
}