CodeForces Dora and C++ (2007C) 题解
题意
给一个数组 \(c_{1...n}\),定义数组的 \(range\) 是最大值减最小值,即极差。给出两个值 \(a\) 和 \(b\),每步操作中,可给数组中任一一个数增大 \(a\) 或增大 \(b\)。问任意步操作后(可以是 \(0\) 步),极差的最小值。
思路
(要直接看答案可以跳过直接看『过程』)
先思考 \(a=b\) 的情况怎么做。我们总能经过不断选最小数使之加 \(a\) 的操作,使数组中的数极差小于 \(a\)。此时可枚举每一个数,即考虑每个 \(c_i(i=1,2,...,n)\),找到该 \(c_i\) 是最小值时,整个数组的情况(方法在后)。对种可能结果,我们取其中最小的,就是答案。
要使 \(c_i\) 是数组中的最小值,即要使所有小于它的数都加上 \(a\),此时我们首先发现:数组中任意数加上 \(a\) 后,都会比原先的最大值大,那么操作后的最大值必然在这些没加上 \(a\) 的值里出现。我们再发现:操作后的最大值,就是所有小于 \(c_i\) 的数中,最大的那个,即是找 \(c_j(j\in \{1, 2, ..., n\} ,\forall c_k \in \{c_k;c_k<c_i,k = 1, 2, ..., n\}),c_j\ge c_k\)。所以,只要找到这个次小于 \(c_i\) 的值 \(c_j\),就能找到这种情况的极差,极差为 \(c_j + a - c_i\),不妨排个序,这样每个结果就是 \(ans_i=\begin{cases}c_{i-1} + a - c_i, \space i>1\\c_n-c_1, \space i=1 \end{cases}\),再取 \(min_{i=1}^n\{ans_i\}\) 即是答案。
当 \(a\neq b\) 时,首先要发现我们可以等价地把某数等价地加或减 \(a\):如果要对某数减 \(a\),等价于给其他数都加上 \(a\);对 \(b\) 同理。再根据裴蜀定理,可知我们总是能对某数加或减 \(d(d=gcd(a,b))\),那么就转化成了第一种情况了。
过程
- 令 \(d=gcd(a,b)\),注意此处不同于题目定义的极差 \(d\)
- \(c_i \gets c_i \space mod \space d,\space i=1,2,...,n\)
- 输出 \(min_{i=1}^n\{ans_i\}\),其中 \(ans_i=\begin{cases}c_{i-1} + d - c_i, \space i>1\\c_n-c_1, \space i=1 \end{cases}\)
代码(C++)
#include <bits/stdc++.h>
#define chmin(a, b) if (a > (b)) a = (b)
using namespace std;
constexpr int N = 1e5 + 3;
int c[N];
int gcd(int a, int b) {
while (b != 0) {
int tmp = a;
a = b;
b = tmp % b;
}
return a;
}
void solve()
{
int n, a, b;
cin >> n >> a >> b;
int d = gcd(a, b);
for (int i = 1; i <= n; ++i) {
cin >> c[i];
c[i] %= d;
}
sort(c + 1, c + 1 + n);
int ans = c[n] - c[1];
for (int i = 2; i <= n; ++i) chmin(ans, c[i - 1] + d - c[i]);
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
标签:...,gcd,space,int,题解,CodeForces,Dora,数组,ans
From: https://www.cnblogs.com/wongdzoendzi/p/18521281