今天蒜头君拿到了一个数轴，上边有 nn 个点，但是蒜头君嫌这根数轴不够优美，想要通过加一些点让它变优美，所谓优美是指考虑相邻两个点的距离，最多只有一对点的距离与其它的不同。
蒜头君想知道，他最少需要加多少个点使这个数轴变优美。
输入格式
输入第一行为一个整数 n(1 \leq n \leq 10^5)n(1≤n≤105)，表示数轴上的点数。
第二行为 nn 个不重复的整数 x_1,x_2,...,x_n(-10^9 \leq x_i \leq 10^9)x1,x2,...,xn(−109≤xi≤109)，表示这些点的坐标，点坐标乱序排列。
输出格式
输出一行，为一个整数，表示蒜头君最少需要加多少个点使这个数轴变优美。
样例输入复制
4 1 3 7 15
样例输出复制
1
思路：
如果不考虑可以有一个区间不同，让我们求的是所有的区间都要优美。至少需要多少个点？
很简单，我们就去求所有区间长度的 求得的就是最小区间长度
考虑最多只有一对点的距离与其他的不同，即此时我们可以去除一个间隔求出 ，那么现在我们要去除哪一个间隔才能使得加点的个数最小呢？
假设某相邻两点之间的距离为 x ，此时我们加点的目标间隔为 ，那么显然我们需要在这两点之间增加 x/−1个点。
综上得出结论，我们期望的 越大越好，因为这样加点的个数会越小。
pos[i]代表去除第 i 个间隔以后的 ，显然它可以通过前缀 与后缀 配合求出。
随后我们找出 pos 中的最大值，设为 maxx ，则 maxx 为解的最优间隔，枚举所有相邻两点的距离，求解需要加点的个数。
可能会出现两种情况：
一、某个区间长度不可以分成符合的倍数的形式。那其实就说明我们去除的就是这个区间。 比如 1，4，4，8 ，8 它的maxx = (4,4,8,8) = 4 那么第一个区间长度1 肯定被去除了
二、所有区间都可以分成符合的倍数的形式。那么我们就去除需要分成份数最多的。 比如4，4，4，8，8 它的maxx = (4,4,4,8,8) = 4 所有区间都可以分成4的倍数，那么我们就去除分成份数最多的区间 8
1 #include <iostream> 2 #include <algorithm> 3 #include <stdlib.h> 4 #include <string> 5 #include <string.h> 6 #include <set> 7 #include <queue> 8 #include <stdbool.h> 9 10 #define LL long long 11 using namespace std; 12 const int MAXN=100005; 13 14 int leftt[MAXN],rightt[MAXN],pos[MAXN]; 15 int a[MAXN],b[MAXN]; 16 int n; 17 18 int (int a,int b) 19 { 20 int t; 21 while (b) 22 { 23 t = b; 24 b = a%b; 25 a = t; 26 } 27 return a; 28 } 29 30 int main() 31 { 32 #ifndef ONLINE_JUDGE 33 freopen("../in.txt","r",stdin); 34 #endif 35 scanf("%d",&n); 36 for (int i=0;i<n;i++) 37 scanf("%d",&a[i]); 38 sort(a,a+n); 39 for (int i=1;i<n;i++) 40 b[i] = a[i]-a[i-1]; 41 leftt[1] = b[1]; 42 for (int i=2;i<n;i++) 43 { 44 leftt[i] = (leftt[i-1],b[i]); 45 } 46 rightt[n-1] = b[n-1]; 47 for (int i=n-2;i>0;i--) 48 { 49 rightt[i] = (b[i],rightt[i+1]); 50 } 51 pos[1] = rightt[2]; 52 pos[n-1] = leftt[n-2]; 53 for (int i=2;i<n-1;i++) 54 pos[i] = (leftt[i-1],rightt[i+1]); 55 int maxx = pos[1]; 56 for (int i=2;i<n;i++) 57 { 58 if (pos[i]>maxx) 59 maxx = pos[i]; 60 } 61 int ans = 0,ms = 0,cnt = 0; 62 for (int i=1;i<n;i++) 63 { if (b[i]%maxx != 0) 65 { 66 cnt++; 67 continue; 68 } 69 ans += b[i]/maxx - 1; 70 ms = max(ms,b[i]/maxx-1); 71 } 72 if (!cnt) 73 ans -= ms; 74 cout << ans << endl; 75 return 0; 76 }