“最不利原则”的应用

· · 题解

写的比较啰嗦详细，相对而言更适合小白阅读。

乍一眼看了一下，这道题很符合最不利原则。

最不利原则就是从最糟糕的情况（也就是极端情况）出发考虑问题。

我们举一个例子：

十个抽屉，五个里装有苹果，问：最少打开几个抽屉才能确保一定找到苹果？

根据最不利原则，我们从最糟糕的情况考虑，最糟糕的情况也就是前五次开盒发现都是空空如也，这时我们已经排除了所有空的抽屉，那么剩下的五个就都是有苹果的抽屉了，随便开一个就好了。

也就是说，如果 p 个抽屉里装有 a 个苹果，我们需要 p - a 次开盒来排除所有空的抽屉，再用一次开盒来找到苹果，总的次数应该为 p - a + 1 次。

所以至少要开六次才能确保一定找到苹果。

这和这道题又有什么关系呢？

分析一下题意，每两个射击的位置之间（或一个射击的位置到边缘）都有一段间隔，如果这段间隔足够长，足以容纳至少一条船，它就可以看做装苹果的抽屉，船就是装在抽屉里的苹果。

那么我们相当于把问题转化成了：

p 个抽屉里有 a 个苹果，每个抽屉至多装一个苹果，问：至少打开几个抽屉才能找到一个苹果？

这个问题我们在上面已经解决过了，答案是 p - a + 1 次。

所以解决这个问题的大致思路我们就理清了，接下来就是细节问题：

首先，如何确定抽屉数量 p 呢？

显而易见地，如果一个空隙能容纳且仅能容纳一条船，这个空隙就可以看做一个抽屉。

比如样例 1：

5 1 2 1
00100

显然，第一段空隙长度为 2，船的长度恰好也为 2，那么可以把第一段空隙视为一个抽屉。

同理，第二段空隙也可以看做一个抽屉，那么对于这组样例，一共有两个抽屉。

那么我们再来看看样例 2：

13 3 2 3
1000000010001

第一段空隙长度为 7，而船的长度为 2，根据高等数学小学数学知识，第一段空隙里至多可以容纳三艘船。

所以，理所应当地，我们把第一段空隙视为三个抽屉。

我们更细致地看待这个过程，首先我们遍历了这个空隙的前两个位置，发现已经足以容纳一艘船，那么这两个位置就被我们视作了一个抽屉，然后我们继续向后遍历。

所以我们只需要在遍历的时候，每次遇到一个 0 就把间隙长度增加，当间隙长度等于 b 的时候，我们在这里放一个抽屉，再将间隙长度归零即可。

解决了这个问题，我们再来看第二个细节，如何实现“打开抽屉”这个操作？

我们回忆一下打开抽屉的目的是什么？其实就是确定一个抽屉是否为空。

也就是说，在执行打开抽屉这个操作之后，我们一定要确保我们已经知道了当前抽屉的状态。

回到题目中，我举个例子：

有一段空隙长为 6，船的长度是 4，那么现在我们要确定这个空隙中有没有船，我们应当如何确定呢？

我们用问号代表一个位置有没有船是不确定的。

??????

假如头脑不太聪明的小明来解决这个问题，他先是射击了一下最左面的位置，发现没有，于是情况变成了这样：

X?????

显然，对于后面五个位置，情况仍然是不确定的，因为这一段的长度依然超过了船的长度，这一段依然可以作为一个抽屉，塞下一艘船。

相当于把抽屉打开一个缝，透过这个缝去看看里面有没有苹果，但是一个缝终究还是太小了，要打开你就大大方方打开啊，开个缝你能看见啥啊。

很显然，一个合适的解决问题的方案是在第四个位置射击，假如没有船，情况就变成了这样：

???X??

此时我们发现，虽然两边我们没有射击，但是它们的长度已经不足以容纳一艘船的长度了，所以可以确定，两边都没有船。

如果我们换到第五个位置射击又会怎么样呢？我们发现，射击之后，即使当前位置没有船，前面的四个位置也足以容纳一艘船了，相当于我们这次射击就是无效的。

所以，当我们已经确定了一个抽屉的位置时，直接到这个抽屉的第 b 位射击就能确定这个抽屉是否为空了。

因为一个抽屉的长度最长为 2b - 1 （因为当一个空隙长为 2b 时，这个空隙将被划分为两个长度为 b 的抽屉），所以在第 b 位射击一定可以同时兼顾前 b 个位置和后 b 个位置的情况，所以针对任何一个抽屉，我们只需在第 b 位设计一次即可解决问题。

细节完善完成，接下来就是代码实现了：


#include <bits/stdc++.h>
using namespace std;
int n, a, b, k;
string s;
int itv;    // interval 用来 
int cnt;    // cnt 用来存储抽屉个数 
int ct[1919810];    // ct 存储每个抽屉的起点 
int main()
{
    cin >> n >> a >> b >> k;
    cin >> s;
    for(int i = 0; i < n; i ++)
    {
        if(s[i] != '0')
            itv = 0;
            // 很好理解，如果当前这个位置已经射击过的话，之前的间隙长度就可以归零了
        else
            itv ++;
            // 反之，间隙长度 +1

        if((s[i] == '0' && s[i - 1] == '1') || (i == 0 && s[i] == '0'))
            // 这里的判断条件式如果一个位置没射击过但前一个位置设计过，那么将这个点存入起点数组中
            ct[cnt] = i;
            // 有的同学可能会担心这样会不会把一些不符合条件的点存进来，其实不需要有这种顾虑
            // 因为只要不符合条件 cnt 就不会增加
            // 这种情况下即使不符合情况的点被加入了数组中，也会被后来符合情况的点覆盖掉
            // 一定还有人想问了，那假如后来没有符合情况的点呢？
            // 好问题，我会在下面解释

        if(itv >= b)
        // 如果当前这个点的间隔已经等于 b 了
        {
            cnt ++;
            // 抽屉数增加
            s[i] = '1';
            // 由于我们在判断起点条件的时候要求起点的前一位必须是 1，所以为了判断下个起点方便，我们直接把这个抽屉的终点设置成 1
            // 理论上讲，这和 ct[cnt] = i + 1 是等价的
            itv = 0;
            // 将间隔设为 0
        }
    }
    cout << cnt - a + 1 << endl;
    for(int i = 0; i < cnt - a + 1; i = i + 1)
        cout << ct[i] + b << " ";
    // 上面的那个问题的解释在这里
    // 看到这个输出，想必你也知道刚才那个问题的答案了
    // 没错，输出的时候最大不能到 cnt - a + 1 处
    // 而 a 最小为 1，所以第 cnt 个位置的起点一定是输入不到的
    // 这样的话，即使这一位不合法也无所谓
    return 0;
}

完美 ~ 撒花✿✿ヽ(°▽°)ノ✿