Uva-1584. Circular Sequence

Uva-340. Circular Sequence 题解

欢迎访问我的Uva题解目录哦https://blog.csdn.net/ri*qi/article/details/81149109

题目描述

题意解析

一个环状的字符序列如果从不同的字符开始顺时针表示的话可以有多种表示方法，要求找出其中字典序最小的一种表示方法。

算法设计

定义一个result变量表示字典序最小串在输入串中的位置，枚举输入串中以各个位置开始的串与以result开始的串进行比较，不断更新result即可。

C++代码

#include<bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i=(a);i<(b);++i)//for循环的一种用宏表示的简写方式
bool compare(const string&s,int a,int b){//比较以a、b位置开始的串的字典序大小
    _for(i,0,s.size())
        if(s[(a+i)%s.size()]!=s[(b+i)%s.size()])
            return s[(a+i)%s.size()]<s[(b+i)%s.size()];
    return false;
}
int main(){
    int T;
    string s;
    scanf("%d",&T);
    while(T--){
        int result=0;
        cin>>s;
        _for(i,1,s.size())
            if(compare(s,i,result))
                result=i;
        _for(i,0,s.size()) putchar(s[(i+result)%s.size()]);
        putchar('\n');
    }
    return 0;
}