自动搬运

查看原文

来自洛谷，原作者为

	Sooke 做被自己雪藏的耳廓狐 | https://codeforces.com/profile/Sulfox

搬运于2025-08-24 21:51:58，当前版本为作者最后更新于2017-04-26 15:31:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

像这一题，要求最远距离最小，必定有二分的份啦~（暴力循环必死）

那么本题除了普通的二分，还有几个坑点（我也是被坑了好几次才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;
}