题目

Description

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，那么训练结束。

Input

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

Output

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

Sample Input

14 5

1

5

3

2

5

1

3

4

4

2

5

1

2

3

Sample Output

3

思路

这道题目乍一看是水题但实际上就***

首先！题目里面说的子序列不是子串！

子串是在一个串里面连续的一段，特别的，空串或这个串也是这个串的子串。

而子序列没这么多要求啊！

它只要求：这个串里出现的元素是在原串里面按顺序出现的就可以了！！！

那么代码实现就很简单了，先实现最大能喊 几次不结束，然后+1输出就可以了。

代码

1 #include
     
       2 using namespace std; 3 int a[100010],c[100010],n,m,k,ans; 4 int read() 5 { 6    int x=0,f=1; 7    char ch=getchar(); 8    while(ch<'0'||ch>'9'){ 9        if(ch=='-')10            f=-1;11        ch=getchar();12    }13    while(ch>='0'&&ch<='9'){14        x=(x<<1)+(x<<3)+(ch^48);15        ch=getchar();16    }17    return x*f;18 }19 int main()20 {21     n=read(),m=read();22     for(int i=1;i<=n;i++)23         a[i]=read();24     for(int i=1;i<=n;i++)25     {26         if(c[a[i]]==ans)27         {28             c[a[i]]++;29             k++;30         }31         if(k==m)32         {33             ans++;34             k=0;35         }36     }37     cout<
      
       <