codeforces 1806C解析

Codeforces 1806C题目链接：https://codeforces.com/problemset/problem/1806/C

题目描述：

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，你可以进行任意多次操作，每次操作可以选择一个区间 $[l,r]$，将区间内的所有数加上 $1$ 或者减去 $1$。你的目标是使得序列中的所有数都相等，求最小的操作次数。

解题思路：

首先考虑对于一个数来说，如何将它变成序列中的所有数。由于每次操作可以将一个区间内的数全部加上或减去 $1$，所以我们可以将该数变成序列中的中位数。中位数是序列中所有数排完序后处在中间的数，如果序列长度为偶数，则中位数是中间两个数的平均数。

接下来考虑对于整个序列来说，如何将所有数变成相等的数。我们可以先将所有数变成中位数，然后计算每个数与中位数的差值之和，这个值就是最小的操作次数。

最后考虑如何将一个数变成中位数。设序列长度为 $n$，$x$ 为中位数，则有以下两种情况：

- 当 $n$ 为奇数时，$x=a_{\lfloor\frac{n+1}{2}\rfloor}$。
- 当 $n$ 为偶数时，$x=\frac{a_{\frac{n}{2}}+a_{\frac{n}{2}+1}}{2}$。

对于第一种情况，我们可以将序列中所有数先减去 $a_{\lfloor\frac{n+1}{2}\rfloor}$，然后再进行操作。

对于第二种情况，我们可以将序列中所有数先减去 $\frac{a_{\frac{n}{2}}+a_{\frac{n}{2}+1}}{2}$，然后再进行操作。注意，当 $n=2$ 时，$\frac{n}{2}=1$，需要特判。

代码实现：