原题链接: AcWing

题目描述:

李华在玩一款叫做《海战》的小游戏，下面是游戏介绍。 给定一个 1×n 的方格矩阵，方格从左到右依次编号为 1∼n。 在这个方格矩阵中，隐藏着 a 个战舰。 每个战舰都占据 b 个连续的方格，每个方格最多只能被一个战舰占据。 每个战舰的具体位置未知。 玩家的任务就是在这种情况下，向一些方格发动精确打击，如果受到精确打击的方格被某个战舰占据着，则视为击中该战舰。 李华已经向 k 个方格发动了精确打击，不幸的是，一个战舰都没有击中。 请你计算，他至少还需要向多少个方格发动精确打击，才能确保自己可以至少击中一个战舰。 请给出一个具体方案。

输入格式

第一行包含 4 个整数 n,a,b,k。 第二行包含一个长度为 n 的 01 字符串，如果第 i 个字符为 1，则表示第 i 个方格已经受到了精确打击，如果第 i 个字符为 0，则表示第 i 个方格还未受到精确打击。保证字符 1 恰好出现 k 次。

输出格式

第一行输出李华还需要发动精确打击的最少方格数量。 第二行输出李华还需要发动精确打击的方格的具体编号，具体输出顺序随意。 如果方案不唯一，输出任意合理方案均可。

数据范围

前 3 个测试点满足 1 ≤ n ≤ 13。 所有测试点满足 1 ≤ n ≤ 2×10^5，1 ≤ a, b ≤ n，0 ≤ k ≤ n−1。

输入样例1：

5 1 2 1
00100

输出样例1：

2
4 2

输入样例2：

13 3 2 3
1000000010001

输出样例2：

2
7 11

解题思路:

这道题是一个模拟题，理解了题意之后发现：只需要遍历把所有能加的战舰就加到数组里，结束时战舰数量−a+1−a+1就是答案，也就是说先把那个所有连续的0算一下，计算可以存放多少个战舰，因为是至少，所以我们假设我们的运气最差，前p.size()-a都没有战舰，那么p.size()-a+1肯定会有战舰。

代码:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
    int n, a, b, k;
    cin >> n >> a >> b >> k;
    string s;
    cin >> s;
    int cnt = 0;
    vector<int> p;
    for (int i = 0;i < s.size();i++)
    {
        if (s[i] == '0')
        {
            cnt++;
            if (cnt == b)
            {
                cnt = 0;
                p.push_back(i + 1);//之所以加1是因为下标是从0开始
            }
        }
        else
        {
             cnt = 0;
        }
           
    }
    cout << p.size() - a + 1<<endl;
    for (int i = 0;i < p.size() - a + 1;i++)
    {
        cout << p[i]<<" ";
    }
}