爱听歌小天鹅

文章
4
资源
0
加入时间
2年10月24天

(赛后补题)G - Occupy the Cities(贪心+二分)两种方法实现

思路:首先是二分,二分需要的时间,然后判断这个时间是否所有的0都可以被攻占,最主要的就是这个check函数了, 我们需要提前把所有0的左右两个方向离他最近的第一个1的位置记录一下,然后就可以开始判断了, 如果两边的1都满足条件,首先选择左边的。纯纯大怨种是我,虽然这题两种方法都可以实现,但是二分的代码量很少,二十分钟就能写出来,而且很好调试,贪心就......写了将近4个小时才调出来的贪心写法,需要想的非常仔细,建议大家直接写二分吧!我这里写的是先分块,将连续的1和连续的0都分成单个元素。