[数据结构与算法]【CF1616B】

传送门

题目

找出str最小的mirror string
可以在任何地方放mirror

思路

从头开始
如果遇到比自己大的 果断放镜子
如果遇到小的 寻找下一位
如果遇到相等的 判断它与开头是否相等
如果相等 则赶紧放mirror
否则 一直遍历所有相等的即可
非常贪心

ac code

//
// Created by 009 on 2022/3/11.
//

// 比前后大小吧
#include<bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        string ans;
        char pre;
        for(int i = 0; i < n; i++) {
            if(i == 0) {
                ans += s[i];
                pre = s[i];
            }
            else {
                // 尽显贪心本色
                // 如果等于却和开始不同 则break，否则继续加入相同的
                if(s[i] > pre || (s[i] == pre && s[i] == ans[0])) break;
                else {
                    ans += s[i];
                    pre = s[i];
                }
            }
        }
        string ans1 = ans;
        reverse(ans.begin(), ans.end());
        cout << ans1 + ans << endl;
    }
}

总结

所谓贪心 就是遍历一遍
求求和 比比较
排排序 找找规律吧