P3718 [AHOI2017初中组] alter
题目描述
有nnn盏灯排成一列，其中有些灯开着，有些灯关着。小可可希望灯是错落有致的，他定义一列灯的状态的不优美度为这些灯中最长的连续的开着或关着的灯的个数。小可可最多可以按开关kkk次，每次操作可以使该盏灯的状态取反：原来开着的就关着，反之开着。现在给出这些灯的状态，求操作后最小的不优美度。
输入格式
第一行两个整数n,kn,kn,k。
第二行是一个长度为nnn的字符串，其中有两种字符：N和F。其中N表示该灯开着，F表示该灯关着。
输出格式
最小的不优美度。
输入输出样例 #1
输入 #1
8 1 NNNFFNNN输出 #1
3说明/提示
30%30\%30%的数据：1≤k≤n≤201\le k \le n\le201≤k≤n≤20；
50%50\%50%的数据：1≤k≤n≤3001\le k \le n\le3001≤k≤n≤300；
另有15%15\%15%的数据：1≤k≤n≤1051\le k \le n\le 10^51≤k≤n≤105，字符串为全N或全F；
100%100\%100%的数据：1≤k≤n≤1051\le k \le n\le 10^51≤k≤n≤105。
本题已经加入 hack 数据。
C++实现
#include<iostream>usingnamespacestd;intmain(){intn,k,p=0,g,t,ans;charc[2]={'F','N'};//灯的状态对应的字符string s;cin>>n>>k>>s;for(inti=0;i<n;i++)if(s[i]==c[i%2])p++;if(p<=k||n-p<=k){cout<<1;return0;}intlb=2,rb=n/k+1,mb;//准备二分while(lb<=rb){mb=(lb+rb)/2;//得出可能的不优美度g=0;for(inti=0,j=0,l=0;i<n;i++){if(s[j]==s[i])l++;elsej=i,l=1;if(mb<l)j=i+1,l=0,g++;}if(g<=k){rb=mb-1;}elselb=mb+1;//根据情况进行二分的分段}cout<<lb;//输出最小的不优美度return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
)
