专栏文章
海亮 2025暑 VIII
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mio6rbp1
- 此快照首次捕获于
- 2025/12/02 14:17 3 个月前
- 此快照最后确认于
- 2025/12/02 14:17 3 个月前
0822
how time flies!
很掉线啊,先不写了。
0823
home! Here we go!
T2
给定一个从小到大排好序的整数序列 A。
现在需要插入一些整数,使得序列中任意相邻两数之间的差值一样大,不能插入在开头和结尾。
问最少插入多少个整数才能满足要求,如果不能,则输出 -1。
由于值域只有 1e6,所以可以直接枚举公差 d 后进行判断。需要做的判断是序列 A 是否为序列b_i=i·d的子序列,总复杂度 O(V log V)。
或者把差分数组求出来,合法的最大公差一定是差分数组的 gcd,可直接完成判断。
注意对边界情况的特判,比如所有元素均相同,n=1,和无解的情况。
CPP#include<bits/stdc++.h>
using namespace std;
int a[10000006];
int b[10000006];
int main()
{
int T;
cin>>T;
while(T--)
{
int ans=0;
int g=0;
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
}
bool flag=0;
for(int i=1; i<n; i++)
{
b[i]=a[i+1]-a[i];
if(b[i]==0) flag=1;
if(b[i]==0 && i==1) g=b[i];
else if(b[i]!=0) g=__gcd(g,b[i]);
}
if(flag && g!=0)
{
cout<<-1<<endl;
continue;
}
if(flag && g==0)
{
cout<<0<<endl;
continue;
}
for(int i=1; i<n; i++)
{
ans=ans+(b[i]/g)-1;
}
cout<<ans<<"\n";
}
return 0;
}
回家了,先不写了。
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...