题解 for 蒜头君的数轴 计蒜客-A1633
题目
今天蒜头君拿到了一个数轴，上边有 n 个点，但是蒜头君嫌这根数轴不够优美，想要通过加一些点让它变优美，所谓优美是指考虑相邻两个点的距离，最多只有一对点的距离与其它的不同。
蒜头君想知道，他最少需要加多少个点使这个数轴变优美。
输入格式
输入第一行为一个整数 n (1≤n≤105)，表示数轴上的点数。
第二行为 n 个不重复的整数 x1,x2,...,xn(−109≤xi≤109)，表示这些点的坐标，点坐标乱序排列。
输出格式
输出一行，为一个整数，表示蒜头君最少需要加多少个点使这个数轴变优美。
样例输入
样例输出
问题分析
根据题意易得出，数轴是否优美取决于相邻两个点的距离。
如果满足下列条件则数轴优美：
- 最多有两种距离
- 若有两种距离，其中的一种距离只有一个。
问题一
我们可以用一个差分数组来表示相邻两个点之间的距离cf[i]
我们先考虑问题一：如果已经排除了那一种距离，如何将剩下的距离变成相同的。
首先我们知道对于任意两个数a，b，我们都可以用x*gcd(a,b)表示出a和b，即**gcd(a,b)**是构成a、b的最小单元。
于是，我们进行推广，对于任意n个数a[n]，我们都可以用**x*gcd(a[n])来表示出所有的数，即gcd(a,b)**是构成a[n]的最小单元。
因此，我们可以得出，当这些距离相同时，他们应该等于gcd(a[n])。
问题二
然后我们处理问题二：如何寻找排除的那一种距离，使得加点的个数最小？
假设某相邻两点之间的距离为 xx ，此时我们加点的目标间隔为 gcd，那么显然我们需要在这两点之间增加 x/gcd−1个点。
综上得出结论，我们期望的 gcd 越大越好，因为这样加点的个数会越小。
那如何实现？
我们可以对差分数组维护一个前缀gcd数组gcd_1和一个后缀gcd数组gcd_2，并设置一个tmp数组，**tmp[i]**表示表去除第 i 个间隔以后的 gcd。
显然 tmp[i]=gcd(gcd1[i−1],gcd2[i+1])
于是我们可以找出tmp中的最大值，设为maxn，则maxn为解的最优距离。根据公式cnt = x/gcd−1
求解加点的个数。
最终处理
同时这里有两种情况：
假设数轴上相邻两个点的间隔分别为：1,4,4,8,8 ，显然去除的距离一定是 1 ，此时 maxn=gcd(4,4,8,8)=4 ，而距离为 1 的这一对点已经被排除过了，因此最少的加点个数为 (4/4−1)+(4/4−1)+(8/4−1)+(8/4−1)=2
假设数轴上相邻两个点的距离分别为：4,4,4,8,8 ，此时去除任意一个距离其结果都一样，因此 $maxx=gcd(4,4,8,8)=4 $，已经不用去除某一个最小值了，我们可以在加点的过程中去除距离最大的那一块（8），最终最少的加点个数为 (4/4−1)+(4/4−1)+(4/4−1)+(8/4−1)+(8/4−1)−(8/4−1)=1
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll a[100005];
ll cf[100005];
ll cf2[100005];
ll gcd_1[100005];
ll gcd_2[100005];
ll tmp[100005];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
for (int i = 1; i < n; i++)
{
cf[i] = a[i] - a[i - 1];
cf2[i] = cf[i];
}
gcd_1[1] = cf[1];
for (int i = 2; i < n; i++)
gcd_1[i] = __gcd(gcd_1[i - 1], cf[i]);
gcd_2[n - 1] = cf[n - 1];
for (int i = n - 2; i > 0; i--)
gcd_2[i] = __gcd(gcd_2[i + 1], cf[i]);
tmp[1] = gcd_2[2];
tmp[n - 1] = gcd_1[n - 2];
long long maxn = tmp[1];
int pos = 1;
for (int i = 2; i < n - 1; i++)
{
tmp[i] = __gcd(gcd_1[i - 1], gcd_2[i + 1]);
if (tmp[i] > maxn)
{
pos = i;
maxn = tmp[i];
}
}
if (tmp[n - 1] > maxn)
{
pos = n - 1;
maxn = tmp[n - 1];
}
long long cnt = 0, ms = 0;
sort(cf2 + 1, cf2 + n);
int cntc = 1;
for (int i = 1; i < n; i++)
{
if (cf2[i] != cf[i - 1])
cntc++;
}
for (int i = 1; i < n; i++)
{
if (i != pos)
cnt += cf[i] / maxn - 1;
ms = max(ms, cf[i] / maxn - 1);
}
if (cnt == 2)
cout << cnt - ms << endl;
else
cout << cnt << endl;
}
|