AT3524 [ARC082A] Together题解

· · 题解

题目传送门

更好的阅读体验

题外话：好像莫得人用双指针诶

Part 1 题意分析

题意：给你 n 个数 a_i，你可以把每个数加一个 \{-1,0,1\} 中的数，然后选择一个所有元素的值相同的子列,求子列长度的最大值。

分析：因为我们要尽可能的把小的数往大加，大的数减小，但我们最大只能加 1，最小也只能减 1，所以这个序列最小最大的数的差一定小于等于 2。如果要求区间长度的最大值那么这个区间最大和最小值的差一定为 2。如果这个序列初始最大和最小值的差就小于等于 2，那么直接输出序列的长度即可。

总结：我们可以先排个序，然后双指针寻找一个差为 2 的长度最大区间，

Part 2 有关双指针

（dalao自动略过，不对，dalao们不会来康我的题解）

双指针算法是指利用两个指针遍历数组（链表），左右指针相向前进或同向前进，在遍历过程中根据某种限制条件进行筛选，通常可以把时间复杂度降低至 O(n)。

一些阔以练习双指针的题

Part 3 代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100001];
int l=1,r=1,t=0;
int ans=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    if((a[n]-a[1])<=2){cout<<n<<endl;return 0;}
    while(r<=n){
        if((a[r]-a[l])<=2){
            r++;
            t++;
            if(t>ans)ans=t;
        }
        else{l++;t--;}
    }
    cout<<ans<<endl;
    return 0;//完结撒花～～
}

AC记录

我的博客

最后的话：看都看了，不点个赞再走嘛？谢谢呐。