Codeforces 977F. Consecutive Subsequence_综合

第一场div3，见识到了题的程度，其实并不难，但是这个题当时还是想了好久没想到的。

You are given an integer array of length $n$ .

You have to choose some subsequence of this array of maximum length such that this subsequence forms a increasing sequence of consecutive integers. In other words the required sequence should be equal to $[x, x + 1, \dots, x + k ? 1]$ for some value $x$ and length $k$ .

Subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order. For example, for the array $[5, 3, 1, 2, 4]$ the following arrays are subsequences: $[3]$ , $[5, 3, 1, 2, 4]$ , $[5, 1, 4]$ , but the array $[1, 3]$ is not.

Input

The first line of the input containing integer number $n$ ( $1 \leq n \leq 2 ? 10^{5}$ ) — the length of the array. The second line of the input containing $n$ integer numbers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ) — the array itself.

Output

On the first line print $k$ — the maximum length of the subsequence of the given array that forms an increasing sequence of consecutive integers.

On the second line print the sequence of the indices of the any maximum length subsequence of the given array that forms an increasing sequence of consecutive integers.

   Examples
  
     input
     
      Copy
     
7
3 3 4 7 5 6 8

     output
     
      Copy
     
4
2 3 5 6 

     input
     
      Copy
     
6
1 3 5 2 4 6

     output
     
      Copy
     
2
1 4 

     input
     
      Copy
     
4
10 9 8 7

     output
     
      Copy
     
1
1 

     input
     
      Copy
     
9
6 7 8 3 4 5 9 10 11

     output
     
      Copy
     
6
1 2 3 7 8 9

Note

All valid answers for the first example (as sequences of indices):

$[1, 3, 5, 6]$
$[2, 3, 5, 6]$

All valid answers for the second example:

$[1, 4]$
$[2, 5]$
$[3, 6]$

All valid answers for the third example:

$[1]$
$[2]$
$[3]$
$[4]$

All valid answers for the fourth example:

$[1, 2, 3, 7, 8, 9]$

题意：给出一个n和n个数的序列，然后让你找到满足两个数之间相差为1的存在的最长的序列，让你输出他们的下标。

大致思路：

跟最长递增子序列差不多，但是他的数据有给的还是挺大的，两种方法，离散化一下，或者map搞一下，map比较好写，所以直接map存一下。接着你只需要保存最长的序列最后一个数的位置和数就可以，那么怎么保存呢？

因为我们需要顺序的从这个序列里找，可以每次把进来的数标记由前面一个数 + 1得到，即可以得到到这个数为止的最长序列的长度。

比如 3 3 4 7 5 6 8

3 的时候我们就以m【2】 + 1 得到这个m【3】，但是因为m【2】没出现过，所以直接就是1，然后下一个3也是如此，4的时候就由m【3】 + 1 ，所以m【4】 = 2，然后依次到8，就可以在m【8】的位置保存到从0到8中，最长的序列长度。

边赋值，边找到最大值的下标和数，然后找到以后，有个最大值，用最大值减去长度 + 1是不是就可以得到他的起始数字了，然后再遍历一遍序列，找每个数就可以了，输出下标。

代码如下

#include <bits/stdc++.h>using namespace std;const int Maxn = 2e5 + 100;
int n,a[Maxn];
map<int,int>m;
int main() {ios::sync_with_stdio(false);while(cin >> n) {m.clear();int len = -1,ans = -1, id;for(int i = 0; i < n; i++) {cin >> a[i];int x = a[i];m[x] = m[x - 1] + 1;if(len < m[x])   len = m[x], ans = x;}int r = ans, l = ans - len + 1;cout <<  len << endl;for(int i = 0; i < n; i++)if(a[i] == l)cout << i + 1 << " ",l++;cout << endl;}return 0;
}