题面

题目描述

N个士兵排成一队进行军事训练，每个士兵的等级用1…K范围内的数来表示，长官每隔1小时就随便说出M个等级a1,a2…am（1≤ai≤K，M个等级中允许有重复），如果这M个等级组成的序列是排成一队的N个士兵等级序列的子序列，那么训练继续；否则训练结束。长官想知道，M至少为多少时，训练才有可能结束。
例：士兵等级序列为1 5 3 2 5 1 3 4 4 2 5 1 2 3，长官说出的等级序列为5 4，那么训练继续，如果长官说出的等级序列为4 4 4，那么训练结束。

输入格式：

第一行为两个整数N和K（1≤N≤100000，1≤K≤10000），下面N行，每行一个数，按队伍顺序表示每个士兵的等级。

输出格式：

包括一行，只包含一个数M，表示当长官至少说出M个等级的时候，训练才有可能结束。

思路

首先看到这道题，先简化题意：找到最短的不是该数列子序列的数列，元素都得在 1 ~ k 里面选

第一个比较傻的想法是：数量最少的数字数量 + 1，显然是不对的。因为假设我就两种状态，1 和 2 然后有 114514 个 1 和 2，那么数数字数量加一答案就是 114515 但是我们要最短，不难想到可以用 2 1 这个序列，也不是原序列的子序列但是长度却短了 114513 。

然后就不难想到，我每次都最大化跳的距离，就可以最短，然后加以就可以了。对，但不多。

仔细思考就发现有很多要思考的点。

  1. 最大化如何最大化：因为我们要子序列，所以只能选这个数后面某一个类型最后出现的哪个类型，如果有重复，子序列判断标准会从第一次出现的开始算
  2. 选完了怎么办：选完了我们就可以直接退出，因为选完了就在我们得出的序列里加上一个，那样就可以最小化

说到这里代码就好写了。这里注意，如果你要按照代码里取出第一个，vector 的 erase 函数是 O(n) 会超时，所以要想代码里一样用指针标出头。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;

int n, k;  
int a[100010];

vector<int >v[10010];
int p[10010];

void Input() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        v[a[i]].push_back(i);
    }
    for(int i = 1; i <= k; i++) {
        p[i] = 0;
    }
}

void Work() {
    int now = 0;
    int ans = 0;
    while(now < n) {
        int pos = 0;
        for(int i = 1; i <= k; i++) {
            while(p[i] < v[i].size() && v[i][p[i]] <= now) {
                p[i]++;
            }
            if(p[i] >= v[i].size()) {
                printf("%d", ans + 1);
                return ;
            }
            // cout << i << " : " << *v[i].begin() << ' ';
            pos = max(pos, v[i][p[i]]);
        }
        // cout << endl;
        ans++;
        now = pos;
        // cout << now << "\n";
    }
    printf("%d", ans + 1);
}

int main() {
    Input();
    Work();
    return 0;
}