题解 | 间隔

间隔

https://ac.nowcoder.com/acm/contest/20105/B

#include <bits/stdc++.h>
using namespace std;
int a[1000010],n,f[1000010];
bool flag;
inline int gcd(int a,int b) {
     return b>0 ? gcd(b,a%b):a;
}
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
	return x*f;
}
int main(){
    for(int T=read();T;T--){
        n=read();
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++) a[i]=read(),f[a[i]]++;
        flag=0;
        for(int i=0;i<=1000000;i++)
            if (f[i]>1&&f[i]!=n) {
                printf("-1\n");
                flag=1;break;
            }
        else if (f[i]==n){
            printf("0\n");
            flag=1;break;
        }
         if (flag) continue; 
        int q=a[2]-a[1];
        for(int i=3;i<=n;i++) q=gcd(q,a[i]-a[i-1]);
        if (q==0){
            printf("-1\n");
            continue;
        }
        else {
            int shu=(a[n]-a[1])/q+1;
            printf("%d\n",shu-n);
        }
    }
	return 0;
}```
因为本题***数据较小***
所以采用**暴力的方法**
首先判断-1的情况+数字全都一样的情况(输出0)
然后在求间隔之间的最大公约数,即为间隔的值
所以按照等差数列求出数字个数-当前的个数,就是新添的数字个数。
如果没看懂
请私信作者
全部评论
和我的代码基本一致!!!
1 回复 分享
发布于 2021-10-17 08:32
点赞 回复 分享
发布于 2021-10-17 08:32

相关推荐

吴offer选手:HR:我KPI到手了就行,合不合适关我什么事
点赞 评论 收藏
分享
豆泥🍀:同26届,加油,我也还没找到查看图片
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务