C. Minimum Notation(简单思维/单调栈/逆序对/归并排序)

题目

题意

给定一个数字字符串，给定操作

每次操作，可以选择任意一个位置上的字符d，

• 将该字符更新为d=min(d+1,‘9’)，
• 并将它移动到任意位置：可以移到任意两个字符中间，也可以移到最前面和最后面。

问经过任意次上述操作，能得到的最小字典序的数字字符串是多少。

常规思路

对于逆序对i s[j] 为了字符串字典序更小，需要将第i位和第j位交换。可以选择移动i，也可以选择移动j，由于移动时，对应的字符会加1，我们选择牺牲更大的i，来保全j。

贪心策略，对于每个存在逆序对的点，我们将大的那个字符，加1。 再全局排序，即可。 至于求每个点是否存在逆序对，我们可以用单调栈。

#include 
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 200010;

int n;
int a[maxn];
char s[maxn];

void solve() {
    scanf("%s", s);
    n = strlen(s);
	stack st; // 单调栈
	for (int i = 0; i  s[i]) {
    		s[st.top()] = min(char(s[st.top()] + 1), '9');
    		st.pop();
		}
		st.push(i);
	}
	sort(s, s + n);
	printf("%s\n", s);
	
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
    	solve();
	}
}

归并排序

我们可以在归并排序过程中，将存在逆序对，需要加1的点，用负号做标记。

注意排序的时候，比较两个相等的字符时，要优先把负数放在后边，因为它更新后，数字加1了。

详见代码。

#include 
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 200010;

int n;
int a[maxn];
int res[maxn];
char s[maxn];
void print_arr(int *arr, int n, string str) {
	printf("%s\n", str.c_str());
	for (int i = 0; i