CF 834B The Festive Evening

xiaoxiao2021-02-28  46

I believe this question can be solve by dp method but I used another way to solve it link is here let’s consider with the greedy method , we can close a opened door as long as the door won’t be used by any quest so we should find the start point and the end point of when the door is open . and we can then maintain a array to find how many segment cover a point and if this point ‘s count is bigger than k then we got answer is “YES”

#include <bits/stdc++.h> #include <cstring> using namespace std; const int maxn = 1e6+1; int st[maxn],en[maxn]; int main() { int vis[30]; int n,k; string str; cin>>n>>k>>str; memset(st,-1,sizeof(st)); memset(en,-1,sizeof(en)); for(int i = 0;i<n;i++) { if(st[str[i]-'A'] == -1) st[str[i] - 'A'] = i; } for(int i = n-1;i>=0;i--) { if(en[str[i] - 'A'] == -1) en[str[i] - 'A'] = i; } int cnt = 0; for(int i = 0;i<n;i++) { if(st[str[i]-'A'] == i) cnt++; if(cnt >k) { return cout<<"YES"<<endl,0; } if(en[str[i] - 'A'] == i) cnt--; } cout<<"NO"<<endl; return 0; }