描述

输入输出格式

输入

输出

输入输出样例

输入样例

14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3

输出样例

3

解题思路

　　首先，我以为这是一道水题，找等级数量最少的就行，然后WA。原来，他要求是子序列（度娘会告诉你的）。然后我就改了改代码。我们把这一列士兵分成几部分，使得每一部分都有所有的等级并且最短，然后只需要把分成的部分的数量加1就可以结束训练了

　　可能还是有点蒙，我们是取极端情况，取每一部分最后一个数，这个数在这一部分只出现了一次，就不会担心子序列连到前面，一直这么连，就求到了最长中最短的情况，再加一就找不到了。

题解

 1 #include
 2 using namespace std;
 3 int n,m,k,ans;
 4 int a[100001],c[100001];
 5 int read()//好用的快读 
 6 {
 7     int x=0,f=1;
 8     char ch=getchar();
 9     while(ch<'0'||ch>'9'){
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9'){
15         x=(x<<1)+(x<<3)+(ch^48);
16         ch=getchar();
17     }
18     return x*f;
19 }
20 int main()
21 {
22     cin>>n>>m;
23     for(int i=1;i<=n;i++)
24         a[i]=read();//输入士兵 
25     for(int i=1;i<=n;i++)
26     {
27         if(c[a[i]]==ans)
28         {
29             c[a[i]]++;
30             k++;//等级数 
31         }
32         if(k==m)
33         {
34             ans++;//部分的数量 
35             k=0;
36         }
37     }
38     cout<1;//加一输出 
39     return 0;
40 }

转载于:https://www.cnblogs.com/hualian/p/11184864.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！