CodeForces

传送门

题意:n个格子上放有a条船,每条船横跨b个格子,已知k个位置上没有船,求再选定最少几个格子,必有一个格子上放有船

输入: n个格子 a条船 b长度 k个已排除位置

  一个01组成的串 0代表不确定,1代表已确定没有船(保证k个1)

输出 选定的格子数

格子的位置

题解:求最少格子,那么如果我们选定的格子上不存在船,都应该做到排除掉尽量多的格子。两个相邻的选定位置距离大于船的长度的话,就会有部分位置不确定,那么选定格子间的距离应刚好等于b。

那么我们在连续的0区间上,每隔长度b选定一个格子,共计cnt个格子。有a艘船,所以我们只要输出任意 (cnt - a + 1) 个位置即可

原文地址:https://www.cnblogs.com/xFANx/p/7403308.html