题解 | #强迫症#

考虑这个操作的本质，就是任意选一组 $i,ji,j$，令 $a_i\leftarrow a_i+a_{j}a\_i\backslash leftarrow\; a\_i+a\_j$。

那么一次至多消除一个重复的数字，所以最优的次数就是重复数字的个数。（例如 $11111~1~1~1$ 就认为有 $33$ 次重复，$2222~2~2$ 就认为有 $22$ 次重复）

考虑证明这个解存在：

把原序列排序，把重复的数字标记出来，然后从后往前做一波 $+=+=$ 的操作就可以了：

例如：

$1112223331\; ~\; \backslash color\{red\}1\; ~\; 1\backslash color\{black\}\; ~\; 2\; ~\; \backslash color\{red\}2\; ~\; 2\; \backslash color\{black\}~\; 3\; ~\; \backslash color\{red\}3\; ~\; 3$

我们直接对红色这些数字进行：

for (int j = len - 1; j >= 1; --j)
  	b[j] += b[j + 1];

的操作，即可把原序列变成：

$1121121083631\; ~\; \backslash color\{red\}12\; ~\; 11\backslash color\{black\}\; ~\; 2\; ~\; \backslash color\{red\}10\; ~\; 8\; \backslash color\{black\}~\; 3\; ~\; \backslash color\{red\}6\; ~\; 3$

肉眼可见这种方法一定是对的。（注意一开始的那一个还要加回来一个最大的 $1212$）

#include<cstdio>
#include<algorithm>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e5 + 5;
int a[N];
int main(){
    int n = init();
    for (int i = 1; i <= n; ++i)
        a[i] = init();
    std::stable_sort(a + 1, a + 1 + n);
    int tot = 0;
    for (int i = 1; i <= n; ++i)
        if (a[i] == a[i - 1]) ++tot;
    print(tot), putchar('\n');
}