题意:
一座城堡有26个入口,分别用26个字母表示,有n个客人,k个守卫。接下来的字符串规定了客人到来时要走哪个门,这个门在客人来之前会打开(注意不是一开始就打开每扇将会有客人进来的门,而是当这位客人快到的时候才打开,也就是说一个个打开)这个门在最后一个客人进去之后才会关闭。同时每次有一个门打开都要有一名士兵去把守,直到最后一个客人进城,他才可以离开去把守别的门。问:会不会出现守卫忙不过来的情况,也就是说出现了门是没有守卫的。
思路:
模拟,先遍历一遍那个顺序,记下关门的时间,然后模拟客人进来就可以了。
#include<iostream>
#include<cstring>
using namespace std;
char orde[1000010];
int main(){int ke,bin;int en[26];int zh[26];cin>>ke>>bin;scanf("%s",orde);memset(zh,0,sizeof(zh));memset(en,0,sizeof(en));for(int i=0;i<ke;i++){en[orde[i]-'A']=i;}int flag=0;for(int i=0;i<ke;i++){if(zh[orde[i]-'A']==0) {zh[orde[i]-'A']=1;bin--;if(bin<0) {flag=1;break;}}if(en[orde[i]-'A']==i)bin++;}if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;return 0;
}