题海拾贝——环状序列（ACM/ICPC Seoul 2004，UVa1584）

        Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：编程之路、 题海拾贝

欢迎点赞关注！

目录

1、题目 

2、分析

3、题解（附详细解析）

1、题目 

       长度为n的环状串有n种表示法，分别为从某个位置开始顺时针得到。例如，abc可以表示为bca，cab，共有三种表示方法。在这些表示法中，字典序最小的成为“最小表示”。

       输入一个长度为n(n<=100)的环状DNA串（只包含ACGT这四种字符的一种表示法，你的任务是输出该环状串的最小表示。例如，CTCC的最小表示是CCCT。

2、分析

       字典序，就是在字典中出现在位置，所以我们只要保证这个表示的第一个位置为ASCII最小的字符就可以了。我们可以通过遍历每一种表示法，比较出最小的那一种。

3、题解（附详细解析）

#include<stdio.h>
#include<string.h>
int less(const char*s,int now,int ans)
{
	int n = strlen(s);
	int i = 0;
	for (i = 0;i < n;i++)
	{
		if (s[(i + now) % n] != s[(i + ans) % n])//注意这里是不等于
		{
			return s[(i + now) % n] - s[(i + ans) % n];//返回值大于0，则说明当下的表示方法更大
			//返回值小于0则当下的表示方法更小
		}
	}
	return 0;//相等
}
int main()
{
	char s[100] = "";
	scanf("%s",s);
	int i = 0;
	int n = strlen(s);
	int ans = 0;//存放当下最小坐标
	for (i = 1;i < n;i++)//比较n次
	{
		if (less(s,i,ans)<0)//i为当下起始坐标，ans为当下最小坐标
		{
			ans = i;//如果当下表示方法更小，则让当下表示方法成为ans
		}
	}
	for (i = 0;i < n;i++)
	{
		putchar(s[(ans + i) % n]);
	}
	return 0;
}

       好了，今天的内容就分享到这，期待我们的下次见面！