CodeForces -977F(突破定式思维+map应用)

题目链接:

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 ;
}
上一篇:hdu 5521 最短路


下一篇:BZOJ 3931: [CQOI2015]网络吞吐量( 最短路 + 最大流 )