清新月饼

文章
9
资源
0
加入时间
2年10月21天

CCPC桂林 - G. Occupy the Cities —— 二分答案

题目来源题意:给定一个长度为 n 的 01 数列。对于每轮操作,如果一个位置上为 1,那么其可以将相邻的最多一个位置上的 0 变成 1。问,将所有 0 都变成 1 至少需要多少轮操作?分析:看这道题之前先看一道简单题:给定一个长度为 n 的 01 数列,对于每轮操作,如果一个位置上为 1,那么其可以将相邻的最多两个位置上的 0 变成 1。问,将所有0 都变成 1 至少需要多少轮操作?对于这道题来说,每个 1 可以向左右两个位置扩展,可以用贪心,也可以二分答案。二分的话,每次 check