Article From:https://www.cnblogs.com/wenzhixin/p/9064340.html

Title Link:

https://cn.vjudge.net/problem/CodeForces-977F

 1 /*
 2 problem 3 Input the number of N and N numbers 4 Calculation and output of the ascending subsequence with the longest increment of 1 5 
 6 The idea of solving the problem 7 It is not feasible to solve the longest ascending subsequence using N2. The scale of n should be (1 N or less than 2*10^5). 8 The map tag is used, and if the length of the current number is assigned to the length of 1 smaller than it is 1, the longest sequence can be reached, and the longest sequence number is found. 9 It can be output in turn.10 */
11 #include<cstdio>
12 #include<iostream>
13 #include<map>
14 #include<vector>
15 using namespace std;
16 
17 map<int,int> mp;
18 int a[205000];
19 int main()
20 {
21     int n,i;
22     int maxk,maxp;
23     vector<int> v;
24     while(scanf("%d",&n) != EOF){
25         mp.clear();
26         maxk=-1;
27         for(i=1;i<=n;i++){
28             scanf("%d",&a[i]);
29             mp[a[i]]=mp[a[i]-1]+1;
30             
31             if(maxk < mp[a[i]]){
32                 maxk = mp[a[i]];
33                 maxp=i;
34             }
35         }
36         
37         v.clear();
38         int st=a[maxp]-maxk+1;
39         for(i=1;i<=n;i++){
40             if(a[i] == st){
41                 v.push_back(i);
42                 st++;
43             }
44             if(st == a[maxp]+1)
45                 break;
46         }
47         
48         printf("%d\n",maxk);
49         for(i=0;i<v.size()-1;i++){
50             cout<<v[i]<<" ";
51         }
52         cout<<v[v.size()-1]<<endl;
53     }
54     return 0;    
55 } 

 

Leave a Reply

Your email address will not be published. Required fields are marked *