Burnling's Blog
0%

CF1712C Sort Zero

发表于 更新于 分类于 ，

题意简述

  • 给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$。
  • 你可以对这些数字进行任意次操作，在每次操作中，
    1. 任选一个正整数 $x$。
    2. 对于序列中所有等于 $x$ 的数字 $a_i$ ，令 $a_i=0$。
  • 寻找让所有数字单调不降所需的最小的操作次数。

题目分析

既然目标是让该序列所有数字单调不降，那么在最终序列中，对于 $\forall i \in [1,n-1]$ ，有 $ai\leq a{i+1}$。

由于每次操作会将一个数代表的值从它自己变为 $0$ ，所以每次操作只会让某个数变小。

所以我们可以从后向前处理这个序列。

令 $A_i$ 表示 $a_i$ 表示的值（若值为 $a_i$ 的数曾被赋值为 $0$ ，则 $A_i=0$ ，否则 $A_i=a_i$）。

那么如果 $Ai \gt A{i+1}$ 则将 $A_i$ 标记为 $0$，表示对于所有的 $a_j=a_i$，令 $a_j=0$。

但是，如果仅仅修改 $A_i$ ，会令出现在 $A_i$ 后面的所有 $x=a_i$ 的值都被修改为 $0$ ，可能会导致序列不满足要求。

所以还需要再从后向前检查并修改若干遍，直到序列符合要求为止。

但是如果每次都从后向前检查的复杂度过高无法接受，所以需要一些优化。

由于每次操作仅会影响到所有值为 $a_i$ 的数字，所以可以从最后一个出现的值为 $a_i$ 的数字开始向前检查。

参考代码

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
40
41
#include<bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 10;

int M[maxN]; //题目分析中的A数组，这里用M代替
int A[maxN]; //原数组
int L[maxN]; //最后出现的值为i的数的下标

int main() {
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		for(int i = 1;i<=N;i++) L[i] = 0;
		
		for (int i = 1; i <= N; i++) {
			cin >> A[i];
			M[A[i]] = A[i]; //最初未被修改时 M[k]=k
		}
		
		for(int i = N;i>=1;i--){
			if(!L[A[i]]) L[A[i]] = i;//从右向左计算L数组
		}

		int cnt = 0;
		
		for (int i = N - 1; i >= 1; i--) { // 从右向左检查并修改
			if (M[A[i]] > M[A[i + 1]]) { //不符合要求，所以进行修改
				M[A[i]] = 0;
				cnt++;
				i = L[A[i]]; //将检查点移到最后出现的被修改值的位置
			}
		}
		
		cout << cnt << endl;
	}
	return 0;
}