Codeforces Round 823 (Div. 2)C

更好的阅读体验

C. Minimum Notation

思路：我们可以进行的操作时将一个位置的数删除然后在任意位置处添加一个比当前数大1并且小于9的数，所以我们的操作只会让一个数变大，我们统计一个最大值的后缀，贪心的考虑如果当前数的后面有比他小的数的话，我们就需要让这个小的数往前走才能使字典序变小，如果当前值小于<= 后缀的最小值，说明这个数后面的所有数往前移动都不能使字典序变得更小，所以我们统计完后缀后，从前往后扫一遍，用multiset维护以下，即可。

#include 

using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
char c[N], suf[N];
void run()
{
	scanf("%s", c + 1);
	int mn = 10;
	int n = strlen(c + 1);
	for(int i = n; i >= 1; -- i)
	{
		int num = c[i] - '0';
		if(num < mn)	mn = num;
		suf[i] = mn;
	} 
	multiset<int>s;
	for(int i = 1; i <= n; ++ i)
	{
		int num = c[i] - '0';
		if(num <= suf[i])	s.insert(num);
		else
		{
			if(num == 9)	s.insert(9);
			else	s.insert(min(num + 1, 9));
		}
	}
	for(auto x : s)	cout << x;
	printf("\n");
}

int main()
{
//	freopen("1.in", "r", stdin);
	int t;cin >> t;
	while(t --)	run();	
	return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39