计蒜客-A1633 程序设计：蒜头君的数轴 题解

题目大意

一个数轴上有n个点，需要满足相邻两点的距离只能有一个不同，如果不满足，可以加点，使满足要求，求最小加点的数量。

解题思路

这题好难想啊。。

首先需要想到n个距离相等，必然是他们累计gcd的倍数。

那么只需要枚举不需要的那一条边即可。

于是就可以用gcd前缀和gcd后缀来简便运算。

推导公式，所需要加点的个数为$(l/gcd)-n+2$。

区间中的点数为$l/gcd-1$，区间中已有的点为n-3，所以公式为$(l/gcd)-n+2$。

之后特判一下起点和终点即可。

注意当$n\leq 2$时，直接输出0，不然会除以0。。（蓝桥的数据还是太水了。。

完整代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1e5 + 5;
int pos[N], dis[N], pre1[N], pre2[N];


int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

int main() {
	int n; cin >> n;
	if (n <= 2) {
		cout << 0 << endl;
		return 0;
	}
	for (int i = 1; i <= n; i++)	cin >> pos[i];
	sort(pos + 1, pos + 1 + n);
	int sum = 0;
	for (int i = 1; i < n; i++)	dis[i] = pos[i+1] - pos[i], sum += dis[i];
	for (int i = 1; i <= n - 1; i++)	pre1[i] = gcd(pre1[i - 1], dis[i]);
	for (int i = n - 1; i >= 1; i--)	pre2[i] = gcd(pre2[i + 1], dis[i]);
	int ans = 2e9;
	for (int i = 1; i < n; i++) {
		int l = sum - dis[i];
		int t;
		if (i == 1)	t = (l / pre2[2]) - n + 2;
		else if (i == n - 1) t = (l / pre1[n - 2]) - n + 2;
		else t = (l / gcd(pre1[i - 1], pre2[i + 1])) - n + 2;
		ans = min(ans, t);
	}
	cout << ans << endl;
}