题目链接:
https://cn.vjudge.net/problem/CodeForces-977F
/*
问题
输入n和n个数的数列
计算并输出最长增量为1的上升子序列 解题思路
用n2的最长上升子序列求解是不可行的,应为n的规模是(1≤n≤2*10^5),所以想到只能用一重循环的算法,
于是使用map标记,如果将当前的数的长度赋值为比它小1的长度加1,可以的到最长的序列,最后找到最长序列记录编号
依次输出即可。
*/
#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
using namespace std; map<int,int> mp;
int a[];
int main()
{
int n,i;
int maxk,maxp;
vector<int> v;
while(scanf("%d",&n) != EOF){
mp.clear();
maxk=-;
for(i=;i<=n;i++){
scanf("%d",&a[i]);
mp[a[i]]=mp[a[i]-]+; if(maxk < mp[a[i]]){
maxk = mp[a[i]];
maxp=i;
}
} v.clear();
int st=a[maxp]-maxk+;
for(i=;i<=n;i++){
if(a[i] == st){
v.push_back(i);
st++;
}
if(st == a[maxp]+)
break;
} printf("%d\n",maxk);
for(i=;i<v.size()-;i++){
cout<<v[i]<<" ";
}
cout<<v[v.size()-]<<endl;
}
return ;
}