题解：P16763 [GKS 2020 #E] Longest Arithmetic

int_long_double · 2026-06-06 11:58:19 · 题解

题面简化：

• 输入：输入一个 T，表示有 T 组数据。接下来 T 组数据中，输入一个 N，表示一个数列的长度为 N，再输入 N 个数。
• 输出：输出一个值，表示数列中最长的等差数列长度。并以格式为 Case #x: y。

  等差数列：

  等差数列在一个数列中（你也可以理解为数组中的一部分），持续上升或下降的，并且他们每两个相近的值差值一样。

  思路：

  这道题数据范围并不大，可以直接暴力枚举，没必要用双指针等优化。

暴力枚举时，不断更新它的长度，并进行打擂台，并且还要记录每一段的差值是多少。最后即可得到答案。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long t;cin>>t;
    for(int i=1;i<=t;i++){
        long long n;cin>>n;
        long long a[1000005];
        cout<<"Case #"<<i<<": ";//格式
        for(int i=1;i<=n;i++) cin>>a[i];
        long long x=a[2]-a[1];//求出首段差值
        long long answer=2,sum=2;//最优、已知
        for(int i=3;i<=n;i++){
            if(a[i]-a[i-1]!=x){//不属于本段等差数列
                sum=2;//这个与上一个的和
                x=a[i]-a[i-1];//差值更新
            }else{
                sum++;//长度增加
            }
            answer=max(answer,sum);//打擂台
        }
        cout<<answer<<endl;//记得换行
    }
    return 0;
}