2019年第十届蓝桥杯省赛C++B组【第八题：等差数列】
·
样例输入
5
2 6 4 10 20
样例输出
10
很水的一道题，目标是包含这N个数的等差数列的项数尽可能小。即这个等差数列是不完整的，中间还空了一点。也就是在满足这N个数成为等差数列的基础上公差尽可能大。
同时根据以下公式易得项数n为多少
等差数列通项公式
an=a1+(n-1)d
an=a1+nd-d
nd=an-a1+d
即
n=(an-a1+d)d
=(an-a1)/d +1
也就是等差数列中的最大值和最小值
n=(max-min)/d +1
因为所给的数是等差数列的一份子，所以我们只要对其排序，相邻位相减就能得到所有有可能等差数列的公差。排序之后a[n-1]就是最大值，a[0]就是最小值，要你说？！
AC代码
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,a[100000],d=LONG_LONG_MAX,sub;
int main(){
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
sub=a[n-1]-a[0];
for(int i=n-1;i>0;i--)
a[i]-=a[i-1];
for(int i=0;i<n;i++)
d=min(a[i],d);
if(!d)cout<<n;//特殊的等差,公差为0,防止RE
else cout<<sub/d+1;
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献9条内容
所有评论(0)