队列及其应用-526互联

问题 K: 连贯子序列
抗病在线，终于搞定了，时间复杂度n^2不让过，优化了半天，终于利用map在nlog下完成了。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+10,INF=0x3f3f3f3f;
int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int a[200010],vis[200010];



void bu_f(){
    int n=read();

    int id=1;int len=1;
    map<int,int> ma;//umap又快了一倍
    for(int i=1;i<=n;i++){
        a[i]=read();
        ma[a[i]]=1;
        if(ma[a[i]-1]) {
            ma[a[i]]+=ma[a[i]-1];//如果刚好小于1值前面出现，就加上他的贡献
            if(ma[a[i]]>len){//更新
                len=ma[a[i]];
                id=i;
            }
        }
    }
    cout<<len<<'\n';
    cout<<id;
}
int main(){
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    // int t=read();
   int t=1;
    while(t--){
        bu_f();
    }
    return 0;
}

队列