Educational Codeforces Round 159 (Rated for Div. 2) C. Insert and Equalize
思路:
首先对 \(a\) 进行排序, 然后对所有差值取gcd ,获得可用的最大因子 \(gc\),
答案有两种情况:
-
一种是 \(a_{n+1}\) 在 $a_1 \(~\) a_n$ 范围内,这时要获得最大的位置
-
一种情况是 $a_1 \(~\) a_n$ 范围内 对 \(gc\) 无空可插入,因此 \(a_{n+1}\) = \(a_n + gc\)
对两种情况:
- 第一种所有数用 \(gc\) 加到 \(a_n\)
- 第二种 所有数用 \(gc\) 加到 \(a_{n+1}\)
#define int long long
#define LL long long
#define ld long double
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
#define ppb pop_back()
#define pb push_back
#define pf push_front
#define so(a) sort(a.begin(),a.end())
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define ikun ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
//mp.reserve(1024);
//mp.max_load_factor(0.25);
using namespace std;
const int N = 1e5 + 10;
vector<int>a;
int gcd(int a, int b)
{
if (b)return gcd(b, a % b);
return a;
}
void solve()
{
a.clear();
int n;
cin >> n;
int x;
fr(i, 1, n)
{
cin >> x;
a.pb(x);
}
so(a);
if (a[0] == a[n - 1])
{
cout << 1 << endl;
return;
}
int gc = a[n - 1] - a[0];
fr(i, 1, n - 1)
{
if (a[i] != a[i - 1])
{
gc = gcd(gc, a[i] - a[i - 1]);
}
}
int ans = 0;
int p = a[n - 1] + gc;
fr(i, 0, n - 1)
{
ans += ( p - a[i]) / gc;
}
p = a[n - 1];
rf(i,n - 1,0)
{
if (p == a[i])
{
p -= gc;
}
else
break;
}
int res = (a[n - 1] - p) / gc;
fr(i,0,n - 1)
{
res += (a[n - 1] - a[i]) / gc;
}
cout << min(ans, res) << "\n";
}
signed main()
{
ikun;
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
标签:Insert,Educational,Rated,int,long,gc,define
From: https://www.cnblogs.com/ikunhuaji/p/17908401.html