题解 P3718 【[AHOI2017初中组]alter】
像这一题，要求最远距离最小，必定有二分的份啦~（暴力循环必死）
那么本题除了普通的二分，还有几个坑点（我也是被坑了好几次才A的）：
-
二分可以求出最小的不优美度，但是当最小值为 1 的时候请特判！
-
注意是最多按几次灯，不是必须要按几次灯！（也就是说，可以不按灯~）
-
二分得出一个可能的不优美度，当超过它而需要按下一个灯的时候，请格外注意赋值的量的大小关系，不要混淆！
这里先重点讲一下特判，由于字符串中的字符不是 N 就是 F ，所以想要让一排灯的不优美度为 1，有两种情况。
以字符串 FNNNFFNN 为例，如果最多能按 4 次开关，求最小的不优美度。
按照上面所说的，可以变成：
-
FNFNFNFN （需要按 3 次开关）
-
NFNFNFNF （需要按 5 次开关）
不难得出，想要让一排灯（灯数 ＞ 1）不优美度为 1 共有两种情况，而变成这两种情况所需要按开关的次数之和正好是灯数。
所以我们只要特判出一种情况，灯数 - 需要按的次数 = 另一种情况需要按的次数。特判两个次数是不是小于等于可以按的次数。
完整的代码如下：
#include <iostream>
using namespace std;
int main()
{
int n,k,p=0,g,t,ans;
char c[2]={'F','N'}; //灯的状态对应的字符
string s;
cin >> n >> k >> s;
for(int i=0;i < n;i++)
if(s[i] == c[i % 2]) p++;
if(p <= k || n-p <= k)
{cout << 1; return 0;}
//上面所说的特判方法
int lb=2,rb=n / k+1,mb; //准备二分
while(lb <= rb)
{
mb=(lb+rb) / 2; //得出可能的不优美度
g=0;
for(int i=0,j=0,l=0;i < n;i++)
{
if(s[j] == s[i]) l++;
else j=i,l=1;
if(mb < l) j=i+1,l=0,g++;
//这个步骤请大家仔细思考。i 表示连续着的灯的最右段， j 表示连续着的灯的最左段，l 表示连续着的灯的长度，g 表示最少需要按多少次灯
}
if(g <= k)
{
rb=mb-1;
} else
lb=mb+1;
//根据情况进行二分的分段
}
cout << lb;
//输出最小的不优美度
return 0;
}