首页 > 代码库 > codeforces 738D

codeforces 738D

  题意:一行1*n的格子放船只,船数为a,船的长度为b,每格为0或1,1表示该格并不是船只的一部分,找出最少的格子数使得射击这些格子至少能打中一艘船。

  思路:船的长度为b,即每段连续的长度为b的0的串都可以放下一只船,射击点为最后一个格子时最优,找出所有的可以放船的位置res个,选择其中的res-a+1个位置。

 

#include<bits/stdc++.h>
using namespace std;
char str[200005];
int op[200005]={0};
int main() {
    int n,a,b,k,cnt=0,tmp,l,t=0;
    scanf("%d%d%d%d%s",&n,&a,&b,&k,str);for(int i=0;i<n;++i) {
        if(str[i]==0) ++t;
        if(str[i]==1) t=0;
        if(t==b) {
            op[cnt++]=i+1;
            t=0;
        }
    }
    cnt-=a-1;
    printf("%d\n",cnt);
    for(int i=0;i<cnt;++i) {
        printf("%d%c",op[i],(i==cnt-1)?\n: );
    }
    return 0;
}

 

codeforces 738D