The Festive Evening time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
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
Note
In the first sample case, the door A is opened right before the first guest's arrival and closed when the second guest enters the castle. The door B is opened right before the arrival of the third guest, and closed after the fifth one arrives. One guard can handle both doors, as the first one is closed before the second one is opened.
In the second sample case, the door B is opened before the second guest's arrival, but the only guard can't leave the door A unattended, as there is still one more guest that should enter the castle through this door.
題意：有26個門，分别是A到Z，現在有n個人想進門，有k個守衛，每個守衛隻能守一個 門，直到自己守得門關
閉為止，才能移動到别的門去守， 每個入口的門在第一個人到達之前被打開，并在最後一個人到達之後
關閉，不能有兩個人同時進一個門。如果在某一時刻至少有一扇門沒有被守，則輸出YES，否則輸出NO
分析：本題wa了5次，從一開始簡單的思路開始wa，然後改正想法，将輸入的數組從前向後周遊，用數組标記字
母第一次出現的位置（數組下标用字母表示，存的值是字母出現的位置），再用一個數組從後往前周遊，标
記第 一個字母出現的位置（也是字母的最後出現位置），但是又wa了，比如這組測試資料：
10 1 ZXCVBNMASZ
本應輸出YES，但按照上述思路則不行。然後還要注意一組資料，如下（本人感覺這題好坑呀）：
10 1 ZXCVBNMASD
不明白的小夥伴結合題意和自己的了解看看如下代碼：
#include<stdio.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000005];//每個字母對應的位置
int b[100];//代表字母第幾次出現
int main()
{
memset(b,0,sizeof(b));
memset(a,0,sizeof(a));
int n,k;
string s;
scanf("%d%d",&n,&k);
cin>>s;
for(int i=0; i<n; i++)
{
if(b[s[i]-'A']==0)
a[i]++;
b[s[i]-'A']++;
}
for(int i=0; i<n; i++)
{
b[s[i]-'A']--;
if(b[s[i]-'A']==0)
a[i+1]--;//自己的門守完後再去别的門守。
}
int sum=0;
int maxx=0;
for(int i=0; i<n; i++)
{
sum+=a[i];
maxx=max(maxx,sum);
}
if(maxx>k)
printf("YES\n");
else
printf("NO\n");
return 0;
}