题目链接:https://codeforces.com/gym/102348/problem/H
题目大意:其实是一道挺水的题目(不然本水题质检员不会有机会做出来的...),就是输入最多3000个整数,让你找其中最长的等差序列的长度,并且输入的数的范围在0~1e18之间。
解题思路:由于本蒟蒻看到3000这个数比较小,心里顿时一番窃喜,便开始了小蒟蒻的暴力解题思路(用到了一点二分)
一开始,我写了下面这坨玩意:
#include<bits/stdc++.h> using namespace std; const int maxn=3200; typedef long long ll; int n; ll int a[maxn]; int main() { scanf("%d",&n); ll mx=0; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } //下面这里是通过暴力枚举每一个首项和每一个公差 for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { ll int di=a[j]-a[i];//公差 ll le=2;//长度 int k=j; //通过二分找到每一个等差序列里面的项 while(k<=n) { ll tmp=a[k]+di; k=lower_bound(a+1+j,a+1+n,a[k]+di)-a; if(a[k]==tmp) { le++; } else { break; } } mx=max(mx,le); } } printf("%lld\n",mx); return 0; }
emmm结果这坨东西就T了,我仔细思考了一下,发现问题在于:如果本身输入的序列就是一个等差序列,而且长度3000的话,那么在我那个while循环哪里就跳不出去,实际上来到了相当于n的3次方的复杂度,于是乎本蒟蒻稍微优化了一下自己的想法:
#include<bits/stdc++.h> using namespace std; const int maxn=3200; typedef long long ll; int n; ll int a[maxn]; int main() { scanf("%d",&n); ll mx=0; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } //下面这里是通过暴力枚举每一个首项和每一个公差 for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { if(n-j<=mx-2) continue; if(mx>=n-i) continue; ll int di=a[j]-a[i];//公差 ll le=2;//长度 int k=j; //通过二分找到每一个等差序列里面的项 while(k<=n) { ll tmp=a[k]+di; k=lower_bound(a+1+j,a+1+n,a[k]+di)-a; if(a[k]==tmp) { le++; } else { break; } } mx=max(mx,le); } } printf("%lld\n",mx); return 0; }
加了两个if之后,就可以把花时间最久的情况给过掉,于是最后的时间是452ms(蒟蒻的侥幸完成任务hhh)