CF Gym102348 H - Berland Prospect

题目链接: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)

上一篇:穿越疫情,阿里云3000万补贴助力中小企业寒冬突围


下一篇:组装电脑配置推荐3000元左右 2021年3000元电脑最强组装