数据结构算法——1034. 构造字典序最小字符串

in
3
2
ba
5
SORTS
10
Sarumanarm

out
case #0:
ab
case #1:
SORST
case #2:
Samranamru

str[l]!=str[r]直接取小的值即可

str[l] == str[r]的时候
观察str[l + 1] 和str[r - 1]的区别
——取两者较小的部分
若str[l + 1] == str[r - 1]
——若str[l+1] > str[l]，那么我们会取完两端再比较剩下的部分//所以这个拿哪个都无所谓
——若str[l+1] == str[l]，我们继续比较l + 2和 r - 2的部分
——若str[l+1] < str[l],我们是先取完两边的相同的部分的其中一份，所以这里还得比较l + 2和 r - 2的部分

#include

using namespace std;

bool greedy(string s, int l, int r)
{
    if(r - l == 1 || r - l == 2)
        return true;//默认右
    else if(s[l + 1] < s[r - 1])
        return false;
    else if(s[l + 1] > s[r] - 1)
        return true;
    else
    {
        return greedy(s, l + 1, r - 1);
    }
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {

        cout << "case #" << i << ":"<> r >> init;
        r--;

        string outcome;
        while(l < r)
        {
            if(init[l] < init[r])
                outcome += init[l++];
            else if(init[l] > init[r])
                outcome += init[r--];
            else
            {
                if(greedy(init, l, r))
                    outcome += init[r--];
                else
                    outcome += init[l++];
            }
        }
        outcome += init[l];
        cout << outcome;

        cout << endl;
    }

    return 0;
}