[C++知识库]C. Minimum Notation(简单思维/单调栈/逆序对/归并排序)

题目

题意

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

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

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

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

常规思路

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

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

#include <bits/stdc++.h>
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<int> st; // 单调栈
	for (int i = 0; i < n; ++i) {
    	while (!st.empty() && s[st.top()] > 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 <bits/stdc++.h>
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 < n; ++i) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}
inline int getOrigin(int x) {
	return abs(x);
}
//Merge Sort
int L[maxn], R[maxn];
void merge(int left, int mid, int right) {
	int n1 = mid - left, n2 = right - mid;
	int i, j, k;
	for(i = 0; i < n1; i++) L[i] = a[left+i];
	for(i = 0; i < n2; i++) R[i] = a[mid+i];
//	print_arr(L, n1, "L");
//	print_arr(R, n2, "R");
	L[n1] = R[n2] = inf; 
	i = j = 0;
	int rev = 0;
	for(k = left; k < right; k++) {
		int tmpL = getOrigin(L[i]);
		int tmpR = getOrigin(R[j]);
		// when tmpL == tmpR, if real value of tmpL not need to add 1, 
		// put it first, otherwise put it second.
		// exp: 
		// realvalue(tmpL) = -8, realvalue(tmpR) = 8
		// tmpL = 8,  tmpR = 8
		// in this case, you need to put tmpL to the second.
		if(i < n1 && (tmpL < tmpR || (tmpL == tmpR && (L[i] > 0 && !rev)))) {
			a[k] = L[i];
			if (rev && a[k] > 0) {
				a[k] = -a[k];
			}
			++i;
		} else {
			rev = 1;
			a[k] = R[j++];
		}
	}
//	print_arr(a + left, right - left, "L+R");
}
void mergeSort(int left,int right) { // mergeSort(0,n)
	if(left+1 < right) {
		int mid = (left + right) / 2;
		mergeSort(left, mid);
		mergeSort(mid, right);
		merge(left, mid, right);
	}
}

void solve() {
    scanf("%s", s);
    n = strlen(s);
    for (int i = 0; i < n; ++i) {
    	a[i] = s[i] - '0';
	}
	mergeSort(0, n);
	for (int i = 0; i < n; ++i) {
		a[i] = a[i] < 0 ? min(-a[i] + 1, 9) : a[i];
    	printf("%d", a[i]);
	}
	printf("\n");
}
int main() {
    int t;
    scanf("%d", &t);
    int cas = 1;
    while (t--) {
//    	printf("case %d:\n", cas++);
    	solve();
	}
}
/*
32454

8428

1202
*/