Circular Sequence--1584

issue description

---

link:https://vjudge.net/problem/UVA-1584
description:

Some DNA sequences exist in circular forms as in
the following figure,
一些DNA序列具有像如图所示的环形形式，
which shows a circular sequence
“CGAGTCAGCT”, that is, the last symbol “T” in
“CGAGTCAGCT” is connected to the first symbol “C”.
最后一个符号T连接着最开始的符号C上，
We always read a circular sequence in the clockwise direction.
我们总是按照顺时针的顺序来读这个环形序列，
Since it is not easy to store a circular sequence in a computer as it is, we decided to store it as a linear sequence.
因此在计算机中很难存储这个环形序列，我们决定把它作为线性序列来存储。
However, there can be many linear sequences that are obtained from a circular sequence by cutting any place of the circular sequence.
但是，这种通过从环形序列的任意位置切分所获的线性线性序列可能有很多种，
Hence, we also decided to store the linear sequence that is lexicographically smallest among all linear
sequences that can be obtained from a circular sequence.
因此，我们决定从环形序列获得的线性序列中选取最小的字典序的作为存储。
Your task is to find the lexicographically smallest sequence from a given circular sequence.
你的任务是从给定的环形序列中找到这个最小序列
For the example in the figure,
从下列图像的例子可知，
the lexicographically smallest sequence is “AGCTCGAGTC”. If there are two or more linear sequences that are lexicographically smallest, you are to find any one of them (in fact, they are the same).

Input
The input consists of T test cases. The number of test cases T is given on the first line of the input
file. Each test case takes one line containing a circular sequence that is written as an arbitrary linear
sequence. Since the circular sequences are DNA sequences, only four symbols, ‘A’, ‘C’, ‘G’ and ‘T’, are
allowed. Each sequence has length at least 2 and at most 100.

Output
Print exactly one line for each test case. The line is to contain the lexicographically smallest sequence
for the test case.

Sample Input
2
CGAGTCAGCT
CTCC

Sample Output
AGCTCGAGTC
CCCT

---

analysis

---

因为lz在考研，但是还是喜欢坚持每天晚上学习一下紫书，刚好题目是英文的，然后就自己努力的翻译着，看不懂的请忽视哈。
把每个分割下来的线性序列看做一个数，然后就变成了从n个数里面选取一个最小值。

---

code

---

#include<iostream>
#include<cstring>
using namespace std;
#define maxn 105
char str[maxn];

int small(int p, int q)
{
    int len = strlen(str);
    for(int i=0; i<len; ++i)
    {
        if(str[(i+p)%len] != str[(i+q)%len])
            return str[(i+p)%len] < str[(i+q)%len]; //p<q，返回1
    }
    return 0; //p>=q返回0
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        cin >> str;
        int len = strlen(str);
        int ans = 0;
        for(int i=1; i<len; ++i)
        {
            if(small(i,ans))
                ans = i;
        }
        for(int i=0; i<len; ++i)
            putchar(str[(ans+i)%len]);
        putchar('\n');
    }
    return 0;
}

---