问题描述
p1584原题链接:UVaOJ 1584 - Circular Sequence
相关说明:本题为《算法竞赛入门经典(第2版)》例题 3-6
解法一:模拟
字典序(lexicographical order)概念题,可以自己实现字符串字典序的比较逻辑(这里选择调用 string.compare 方法)。另外需要实现一个循环左移 k 位操作(对于此题 k==1 ),可以当成是拆开成两个子串 s1+s2 的调换位置拼接,变成 s2+s1, 记得在多次左移操作的同时比较字典序维护 ans 的值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { string seq; cin >> seq; if (seq.length() == 1) { cout << seq << endl; continue; } string cur = seq, ans = seq; for (int i = 1; i < seq.length(); ++i) { cur = cur.substr(1, cur.length() - 1) + cur.substr(0, 1); if (cur.compare(ans) < 0) ans = cur; } cout << ans << endl; } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 |
t = int(input()) for _ in range(t): seq = input() if len(seq) == 1: print(seq) continue cur = ans = seq for i in range(1, len(seq)): cur = cur[1:len(cur)] + cur[:1] if cur < ans: ans = cur print(ans) |