首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。