C/C++教程

Acwing_4394 最长连续子序列

本文主要是介绍Acwing_4394 最长连续子序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 

 题目来自:https://www.acwing.com/problem/content/4397/

笔者做的时候想着能不能去动态调整记录表,但最终的简化策略其实是往维护双指针区间上面靠的,以下是答案代码;

循环再动态维护一个从l到r的区间,将移动过的地方取消标记并判断是否产生 异值 数量的变化,对于向右的拓展也是如此,不过循环内这些代码并不能随意写,要遵照  1.更新结果时必须是合法状态 2.必须有结束循环的迭代和判断 3.必须在迭代之后判断状态合法性。

#include <bits/stdc++.h>
using namespace std;
int x[500005];
int f[1000005]= {0};
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=0; i<n; i++) cin>>x[i];
    int l=0,r=0;
    int ansl=0,ansr=0;
    f[x[r]]++;
    int limit=1;
// 从现在开始像毛毛虫一样向右滚动 ][->[]->[ ]->[  ]->[   ]->[    ]->_[  ]->_[   ]   
    while(r<n){
//        在和发状态下双指针更新结果 
        (r-l+1>ansr-ansl+1) && (ansl=l,ansr=r);
//        双指针迭代 
        limit+=(f[x[++r]]++)==0;
//        双指针判断合法性并处理 
        (limit>k) && (f[x[l]]--,f[x[r]]--,limit-=(f[x[l]]==0)+(f[x[r]]==0),l++,r--);
    }
    cout<<ansl+1<<" "<<ansr+1;
    return 0;
}

(表达式)&&(表达式)其实 可以当个if用,前面的为真后面的才会执行,因为与判断程序从左向右度,如果遇到真就接着判断下一个,如果为假那整个式子直接返回假,后面的就不执行了。之前笔者遇到的一个快读部分代码写法也是这样的,虽然并不能提升多少算法能力,但遇到相似的可以看懂,而且似乎很酷的样子。

 

这篇关于Acwing_4394 最长连续子序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!