思路

来分析分析样例：

3

-5 10 5

我们把它升序排列，会得到这个东西↑

不仔细地观察后可以发现：加一个（0，0）的点显然是最优的

再用脚趾头想想为什么，我们发现，这题题意就是想让我们把一段线段x等分，使得给出的点都是它的x等分点。

而通过我们的敏锐的第六感做题经验，不难看出最优解即相邻点距离的最大公约数

做法

显然此题难点在于求n个数的gcd

而要求多个数的gcd，两两求之后合并即可。

证明：

以三个数为例，设有a,b,c三数，x=gcd(a,b),y=gcd(x,c)，因为a%x=0，x%y=0，所以a%y也等于零，且y是符合条件的最大值。

所以我们可以递推求n个长度的gcd，然后出解即可

代码

#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

int a[100001];

int b[100001];

int main()

{

int n;

cin >> n;

for ( int i = 1; i <= n; i++ )

{

cin >> b[i];

}

sort ( b + 1, b + n + 1 );

for ( int i = 2; i <= n; i++ )

a[i] = b[i] - b[i-1];

int dis = b[n] - b[1];

for ( int i = 2; i <= n; i++ )

{

a[i] = __gcd( a[i], a[i-1] );

//在<cmath>里的神奇函数（妈妈再也不用担心我不会辗转相除啦！）

}

cout << dis / a[n] - n + 1;

/*此时的a[n]即为最优的线段长度，dis/a[n]为线段个数，

再加1是点的个数，最后减去原有的n个点，输出*/

return 0;

}

完美收官（你们没发现开头的链接是两个吗）

巴特西

CF926B Add Points

更好的 阅读体验

思路

做法

代码

最新文章

热门文章