https://codeforces.com/contest/1902/problem/C
题目大意
给出 $n \ (\le 2 \times 10^5)$ 长的数组 $a$ 其中 $-10^9 \le a_i \le 10^9$，且元素不重复。给 $a$ 添加任意其中未出现的元素 $a_{n + 1}$ 后，对于新数组，可以选定某固定 $x$ 后，对数组执行若干次，选定某 $a_i$ 然后 $a_i \gets a_i + x$。问选取最佳的 $a_{n + 1}$ 和 $x$ 之后，最少的操作次数使得整个数组所有元素相同。
简要题解
先考虑不加入新数字。将数组排序，假定最终的目标数字为 $y \ge a_n$，则显然 $x = gcd_{i}(y - a_i)$，注意到由于 $gcd$ 的性质，我们可以将这个式子改写为 $x = gcd(gcd_{i}^{n - 1} (a_{i+1} - a_i), y - a_{n})$。假定 $y_0 = a_n$，此时对应 $x$ 为 $x_0$ 以及总差量为 $sum_0 = \sum_i y - a_{i}$，对应的答案为 $ans_0 = sum_0 / x_0$。 当 $y > a_n$ 时 $x <= x_0$，而 $sum > sum_0$ 即最终 $ans > ans_0$。
在此基础上我们考虑 $a_{n+1}$。先考虑不改变 $x$。这里原先的 $a$ 相当于某个等差数列的某些项，我们就是找到这个等差数列中小于 $a_n$ 且，最大的没选的项，此时我们可以有最小的增量。如果选大于 $a_n$ 的量，即使是 $a_n + x$ 作为 $a_{n + 1}$ 也不会比前面的方案更优，因为这样至少需要多 $n$ 次将值调整到 $a_{n + 1}$，而即便是 $a_{n + 1} = a_n - nx$ 的情况（刚好原 $a_i = a_n - (n - i)x$）也不会比用 $a_n + x$ 的更差。
如果新加入的值改变了 $x$ 则只会让 $x$ 更小，此时 $x$ 至少变为原先的一半（因为至少要少一个因子）因此这至少会让 $ans0$ 翻倍。而对于 $n \ge 3$ 的情况，$ans_0 \ge n$，则翻倍后不会比情况 $x$ 不变的最差情况更好。$n = 1$ 是平凡的。对于 $n = 2$，这也同样是没有意义的，因为 $3$ 个数最少的操作次数就是 $3$ 次，不改变 $x$ 的方案已经达到了这个下界。
复杂度
$T$：$O(n \log \max(a))$
$S$：$O(n \log \max(a))$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
if (n == 1) {
cout << "1\n";
return;
}
sort(a.begin(), a.end());
int g = 0;
for (int i = 1; i < n; i++) {
g = gcd(g, a[i] - a[i - 1]);
}
LL ans = 0;
for (int i = 0; i < n; i++) {
ans += (a[n - 1] - a[i]) / g;
}
// cerr << g << ' ' << ans << '\n';
for (int i = n - 1; i >= 0; i--) {
if (a[i] != (a[n - 1] - g * (n - 1 - i))) {
cout << (ans + (n - 1 - i)) << '\n';
return;
}
}
cout << (ans + n) << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. Getting Points - Educational Codeforces Round 159 (Rated for Div. 2)