计蒜客 25092 蒜头君的数轴

题目描述

今天蒜头君拿到了一个数轴，上边有 $n$ 个点，但是蒜头君嫌这根数轴不够优美，想要通过加一些点让它变优美，所谓优美是指考虑相邻两个点的距离，最多只有一对点的距离与其它的不同。

蒜头君想知道，他最少需要加多少个点使这个数轴变优美。

输入格式

输入第一行为一个整数 $n(1 \leq n \leq 10^5)$，表示数轴上的点数。

第二行为 $n$ 个不重复的整数 $x_1,x_2,…,x_n(−10^9≤xi≤10^9)$，表示这些点的坐标，点坐标乱序排列。

输出格式

输出一行，为一个整数，表示蒜头君最少需要加多少个点使这个数轴变优美。

样例输入

4
1 3 7 15

样例输出

1

思路

由题意可以知道，数轴是否优美与相邻两个点的距离有关，假设我们暂时不考虑最多只有一对点的距离与其他的不同，那么最终我们加完点之后的间隙大小便等于此时所有间隔的 gcd，于是我们可以求出间隔 gcd，然后此时相邻两个点之间所要添加的点的个数便可以直接计算得到了。

考虑最多只有一对点的距离与其他的不同，即此时我们可以去除一个间隔求出 gcd，那么现在我们要去除哪一个间隔才能使得加点的个数最小呢？

假设某相邻两点之间的距离为 $x$ ，此时我们加点的目标间隔为 $gcd$，那么显然我们需要在这两点之间增加 $x/gcd-1$ 个点。

综上得出结论，我们期望的 $gcd$ 越大越好，因为这样加点的个数会越小。

$pos[i]$ 代表去除第 $i$ 个间隔以后的 $gcd$ ，显然它可以通过前缀 gcd 与后缀 gcd 配合求出。

随后我们找出 $pos$ 中的最大值，设为 $maxx$ ，则 $maxx$ 为解的最优间隔，枚举所有相邻两点的距离，求解需要加点的个数。

这里有两种情况：

1. 假设数轴上相邻两个点的间隔分别为：$1,4,4,8,8$ ，显然去除的间隔一定是 $1$ ，此时 $maxx=\gcd(4,4,8,8)=4$ ，而间隔为 $1$ 的这一对点已经被消耗过了，因此最少的加点个数为 $(4/4-1)+(4/4-1)+(8/4-1)+(8/4-1)=2$
2. 假设数轴上相邻两个点的间隔分别为：$4,4,4,8,8$ ，此时去除任意一个间隔其结果都一样，因此 $maxx=gcd(4,4,8,8)=4$ ，这里并没有像上一种情况中因为某个间隔会拉低整体 gcd 而消耗掉“最多只有一对点的距离与其他的不同”这一个机会，因此我们可以在加点的过程中去除间隔最大的那一块，最终最少的加点个数为 $(4/4-1)+(4/4-1)+(4/4-1)+(8/4-1)+(8/4-1)-(8/4-1)=1$

AC 代码

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;

int leftt[maxn],rightt[maxn],pos[maxn];
int a[maxn];
int b[maxn];
int n;

void init()
{
    leftt[1] = b[1];
    for(int i=2; i<n; i++)  //前缀 gcd
        leftt[i] = __gcd(leftt[i-1],b[i]);

    rightt[n-1] = b[n-1];
    for(int i=n-2; i>0; i--)    //后缀 gcd
        rightt[i] = __gcd(rightt[i+1],b[i]);

    pos[1] = rightt[2];
    pos[n-1] = leftt[n-2];
    for(int i = 2; i<n-1; i++)  //去除i后的gcd
        pos[i] = __gcd(leftt[i-1],rightt[i+1]);

    int maxx = pos[1];
    for(int i=2; i<n; i++)
        if(pos[i]>maxx)
            maxx = pos[i];

    int ans = 0,ms = 0,ct = 0;
    for(int i=1; i<n; i++)
    {
        if(b[i] % maxx != 0)
        {
            ++ct;
            continue;
        }
        ans += b[i] / maxx - 1;
        ms = max(ms,b[i] / maxx - 1);
    }
    if(!ct)     //如果没有哪个间隔拉低整体 gcd，减掉间隔最大的那一块
        ans-=ms;
    cout<<ans<<endl;
}

int main()
{
    IO;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=1; i<n; i++)
        b[i] = a[i] - a[i-1];
    init();
    return 0;
}