CF1902C

题解 · 2023-12-10

题意

给你一个整数数组 $a_1, a_2, \dots, a_n$ ,它的所有元素都是不同的。

首先,要求你在这个数组中再插入一个整数 $a_{n+1}$ 。 $a_{n+1}$ 不应等于 $a_1, a_2, \dots, a_n$ 中的任何一个。

然后,您必须使数组中的所有元素相等。开始时,您选择一个正整数 $x$。在一次操作中,你将 $x$ 恰好添加到数组的一个元素中。注意 $x$ 在所有操作中都是一样的

在你选择了 $a_{n+1}$ 和 $x$ 之后,要使所有元素相等所需的最小运算次数是多少?

题解

由于 $x$ 只能是正值,所以我们只能使所有元素等于数组中当前的最大值。

考虑不添加 $a_{n + 1}$。我们设 $a$ 中最大值为 $M$,则要想要运算次数最少,则需要使 $x$ 尽可能大,所以 $x$ 应该取 $gcd\{a_n -a_1, a_n-a_2, \dots, a_n-a_{n-1}\}$,然后直接枚举统计答案即可。

考虑添加 $a_{n+1}$。我们不希望改变 $x$(将会增加至少 $n$ 的答案),所以我们选择当 $a_{n+1} = M - k \cdot x$ 时 $k$($k > 0$) 使 $k$ 尽量小,且不与 $a$ 中元素重复。

Code:

#include <algorithm>
#include <iostream>
#include <map>
#pragma GCC optimize (3)
using namespace std;
typedef long long ll;
const int maxn = 200010;
int t;
ll ans, a[maxn], x;
int n;
map <ll, bool> p;
int main () {
  ios::sync_with_stdio (false);
  cin.tie (0);
  cin >> t;
  while (t--) {
    cin >> n;
    p.clear ();
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      p[a[i]] = true;
    }
    sort (a + 1, a + n + 1);
    x = a[n] - a[1];
    ans = 0;
    for (int i = 2; i < n; i++) {
      x = __gcd (x, a[n] - a[i]);
    }
    x = max (x, 1ll);
    for (int i = 1; i < n; i++) ans += (a[n] - a[i]) / x;
    for (ll i = a[n]; ; i -= x) {
      if (!p[i]) {ans += (a[n] - i) / x; break;}
    }
    cout << ans << '\n';
  }
  return 0;
}
题解
Theme Jasmine by Kent Liao