思路
首先可以发现前三个数中的两个数一定为一个等差数列中,所以我们对于前三个数枚举哪两个数是一个等差数列中的,设这两个数的差为 \(w\),在原数列中找到一个最长的公差为 \(w\) 的等差数列,记为 \(A\),剩下的数记为 \(B\),此时有三种可能。
- \(|B|=0\),此时可以知道原数组就是等差数列,此时我们可以把 \(B\) 当成最后一个数即可。
- \(|B|\leq 2\),通过题意可知 \(B\) 也为等差数列,直接输出即可。
- \(|B|>2\),此时答案不一定不存在,有可能在 \(A\) 中选择一些数到 \(B\) 后能使 \(B\) 成为等差数列,为了仍满足 \(A\) 为等差数列,所以我们取出的这段数一定要为 \(A\) 的后缀,然后插入进 \(B\) 中,这个过程可以用set来维护,但是我们想要快速维护 \(B\) 是否为等差数列仍需要知道序列的公差,所以我们可以枚举公差,而有效的公差只有 \(B\) 的最后两位的差和 \(A\) 与 \(B\) 最后两位的差。
代码
#include<bits/stdc++.h>
#define mm 600010
using namespace std;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,a[mm];
int A[mm],B[mm];
int num1,num2;
set<int> s;
bool vis[mm];
void check(int w)//将A的后缀插入到B中
{
s.clear();int add=0;
for(int i=2;i<=num2;i++)if(a[B[i]]-a[B[i-1]]!=w) ++add;
for(int i=1;i<=num2;i++)s.insert(B[i]);
for(int i=num1;i>=0;i--)
{
if(add==0)
{
if(i==0)
{
printf("%d\n",a[1]);
for(int j=2;j<=n;j++) printf("%d ",a[j]);printf("\n");
exit(0);
}
for(int j=1;j<=i;j++)printf("%d ",a[A[j]]),vis[A[j]]=true;printf("\n");
for(int j=1;j<=n;j++)if(!vis[j])printf("%d ",a[j]);printf("\n");
exit(0);
}
if(i==0) break;
int X=A[i];
s.insert(X);
auto it=s.lower_bound(X);
auto it1=it;it1--;auto pre=it1;
auto it2=it;it2++;auto nxt=it2;
if(it==s.begin())
{
if(a[*nxt]-a[*it]!=w) ++add;
continue;
}
if(it==s.end())
{
if(a[*it]-a[*pre]!=w) ++add;
continue;
}
if(a[*nxt]-a[*pre]==w){add+=2;continue;}
if(a[*it]-a[*pre]!=w && a[*nxt]-a[*it]!=w) ++add;
else if(a[*it]-a[*pre]==w && a[*nxt]-a[*it]==w) --add;
//插入一个数,动态维护B是否为等差数列
}
}
void work(int sta,int w)
{
num1=num2=0;
for(int i=1;i<sta;i++) B[++num2]=i;
for(int i=sta;i<=n;i++)
if(a[i]-a[A[num1]]==w || i==sta) A[++num1]=i;
else B[++num2]=i;
if(num2==0)
{
for(int i=1;i<num1;i++) printf("%d ",a[A[i]]);printf("\n");
printf("%d\n",a[A[num1]]);
exit(0);
}//情况1
if(num2<=2)
{
for(int i=1;i<=num1;i++) printf("%d ",a[A[i]]);printf("\n");
for(int i=1;i<=num2;i++) printf("%d ",a[B[i]]);printf("\n");
exit(0);
}//情况2
check(a[B[num2]]-a[B[num2-1]]);
check(a[B[num2]]-a[A[num1]]);
check(a[A[num1]]-a[B[num2]]);
//情况3
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
work(1,a[2]-a[1]),work(1,a[3]-a[1]),work(2,a[3]-a[2]);//枚举哪两个数在同一个等差数列中
puts("No solution");
}
标签:ch,int,题解,公差,add,CF125D,等差数列
From: https://www.cnblogs.com/noipwen/p/18001885