Codeforces Round 834B-The Festive Evening

本文主要是介绍Codeforces Round 834B-The Festive Evening，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

It’s the end of July – the time when a festive evening is held at Jelly Castle! Guests from all over the kingdom gather here to discuss new trends in the world of confectionery. Yet some of the things discussed here are not supposed to be disclosed to the general public: the information can cause discord in the kingdom of Sweetland in case it turns out to reach the wrong hands. So it’s a necessity to not let any uninvited guests in.
There are 26 entrances in Jelly Castle, enumerated with uppercase English letters from A to Z. Because of security measures, each guest is known to be assigned an entrance he should enter the castle through. The door of each entrance is opened right before the first guest’s arrival and closed right after the arrival of the last guest that should enter the castle through this entrance. No two guests can enter the castle simultaneously.
For an entrance to be protected from possible intrusion, a candy guard should be assigned to it. There are k such guards in the castle, so if there are more than k opened doors, one of them is going to be left unguarded! Notice that a guard can’t leave his post until the door he is assigned to is closed.
Slastyona had a suspicion that there could be uninvited guests at the evening. She knows the order in which the invited guests entered the castle, and wants you to help her check whether there was a moment when more than k doors were opened.

Input

Two integers are given in the first string: the number of guests n and the number of guards k (1 ≤ n ≤ 106, 1 ≤ k ≤ 26).
In the second string, n uppercase English letters s1s2… sn are given, where si is the entrance used by the i-th guest.

Output

Output «YES» if at least one door was unguarded during some time, and «NO» otherwise.
You can output each letter in arbitrary case (upper or lower).

Examples

Input
5 1
AABBB
Output
NO
Input
5 1
ABABB
Output
YES

一座城堡有26个门，分别用A~Z表示。有n位客人要进入这个城堡。客人进入城堡需要通过这些门。
每一道门，在第一位客人进来先打开，在通过这道门的最后一位客人进入以后关闭。
（一个潜在的坑= =）
城堡的主人为这些门配备了k位守卫。守卫不可以在某一道门没有关上的情况下离开这道门，以防止有多位客人同时通过一道门的情况。给出n、k以及客人们进入门的顺序。求有没有可能发生有超过k个门打开的情况。

我的做法是，记录下每一道门打开的时间和门关上的时间。
为了方便起见我用了map来实现。
mp1记录每道门打开的时间。mp2记录门关闭的时间。
时间用客人的进门的次序来表示。用一个变量m来记录，每一个时刻，有多少个门开着。
根据客人进门顺序从头到尾遍历，查询有没有哪个时刻，有超过k个门开着，如果有直接break，输出结果YES

不过有一个坑是在题目的描述上。
题目上说了，门是在客人到来之前就打开的。
也就是说，并不是客人来了你才去开门，而是前一个客人进门的时候守卫就需要去开门的。
最开始没有考虑这个点，在第四个test就WA了。
所以这个题目，在一开始，第一位客人要进入的那个门就是开着的。
所以m的初始值我设为1，当遍历到当前的客人时，查询下一个门此时是否应该开启。
如果不考虑这种情况的话，有可能有超过k个门开启的情况会被漏掉。
这是需要注意的点。

具体代码如下：

#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
#include<stdio.h>
#include<cstdio>
#define Max 100000using namespace std;
map<char,int> mp1,mp2;//开始、结束void f()
{char c='A';for(; c<='Z'; c++){mp1[c]=-1;mp2[c]=-1;}
}void clr()
//清空
{mp1.clear();mp2.clear();
}int main()
{char a,b,c;string s;bool flag;int T;int i,j,k,t;int m,n,l;bool flag1,flag2;while(cin>>n>>k){cin>>s;clr();f();flag=true;for(i=0; i<n; i++){if(mp1[s[i]]==-1)
//判断开始值是否已存在mp1[s[i]]=i;mp2[s[i]]=i;
//一直更新mp2[s[i]]值，这样最后保存下来的一定是最晚的那个客人的进门时间}for(j=0,m=1; j<n; j++){if(j+1==mp1[s[j+1]])
//考虑下一位客人进入的门是否需要打开m++;if(j==mp2[s[j]])
//当前客人进入的门是否需要开启m--;if(m>k){flag=false;break;}}if(flag)printf("NO\n");else printf("YES\n");}return 0;
}