Two Operations Gym – 102263M

Ayoub has a string SS consists of only lower case Latin letters, and he wants you to make some operations on it:

  1. you can swap any two characters in the string.
  2. you can delete any two adjacent characters that have the same value and replace them with the next character alphabetically,for example string “abbx““abbx” could be “acx““acx” after one operation, string “zz““zz” could not be changed; because z is the last character in the English alphabets.

Ayoub wants you to make the string lexicographically maximal using the mentioned operations as many times as you want, can you help him?

String x=x1x2...x|x|x=x1x2…x|x| is lexicographically larger than string y=y1y2...y|y|y=y1y2…y|y|, if either |x|>|y||x|>|y| and x1=y1,x2=y2,...,x|y|=y|y|x1=y1,x2=y2,…,x|y|=y|y|, or exists such number r(r<|x|,r<|y|)r(r<|x|,r<|y|), that x1=y1,x2=y2,...,xr=yrx1=y1,x2=y2,…,xr=yr and xr+1>yr+1xr+1>yr+1. Characters in lines are compared like their ASCII codes.

Input

　　The input contains a single string SS (1≤|S|≤105)(1≤|S|≤105).

　　It is guaranteed that string SS consists of only lower case Latin letters.

Output

　　print the lexicographically maximal string that could be obtained using these two operations.

#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;

priority_queue <char, vector<char>, greater<char> >q1;//从小到大优先排序
priority_queue <char, vector<char>, less<char> >q2;//从大到小优先排序
int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        q1.push(s[i]);
    }
    while (!q1.empty()) {
        char top = q1.top();//获取栈顶
        q1.pop();
        if (!q1.empty() && top != 'z') {
            if (top == q1.top()) {//合并插入
                q1.pop();
                    q1.push(top + 1);
            }
            else {
                q2.push(top);
            }
        }
        else {
            q2.push(top);
        }
    }
    while (!q2.empty()) {
        char head = q2.top();
        q2.pop();
        cout << head;
    }
    return 0;
}

 

版权声明：本文为C-U-Again原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/C-U-Again/p/12896127.html