1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include<bits/stdc++.h> #define ll long long #define N 100010 #define fsb(a,b,c) for(int a=b;a<=c;a++) #define fbs(a,b,c) for(int a=b;a>=c;a--) using namespace std; int n,m,a[N],l,r,mid,b[N],cnt=0; char s[N]; inline void work(){ int last=2; fsb(i,1,n) if(a[i]!=last){ b[++cnt]=1;last=a[i]; }else b[cnt]++; } inline int check(int x){ int cnt1=0; fsb(i,1,cnt)cnt1+=b[i]/(x+1); return cnt1<=m; } int main(){ scanf("%d%d",&n,&m);scanf("%s",s+1); fsb(i,1,n)a[i]=s[i]=='N'?1:0; work(); int cnt2=0; fsb(i,1,n){ if(a[i]+(i&1)==1)cnt2++; } if(cnt2<=m||n-cnt2<=m){ puts("1");return 0; } l=2;r=n; while(l+5<r){ mid=(l+r)>>1; if(check(mid))r=mid;else l=mid; } fsb(i,l,r)if(check(i)){ printf("%d\n",i);return 0; } return 0; }
|