题解 洛谷 Luogu P3853 [TJOI2007] 路标设置 二分答案 C/C++

题目传送门：

P3853 [TJOI2007] 路标设置 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/problem/P3853思路：

二分答案，每次询问区间 [l, r] 中点 m 是否为合法距离

是就记录答案并试图找更小的合法距离，将区间改为 [l, m - 1]，否则改为 [m + 1, r]

如何判断 m 是否为合法距离？

(相邻路标距离 - 小于 1 的小数) / m 即为这两个路标之间应增设的路灯数

减去小于 1 的小数是考虑到了边界情况

如距离为 80，m 为 20，80 / 20 = 4，而我们只需要增设 3 个路标

全路段应增设的路标数不大于 k 就是合法的

代码：

#include <cstdio>
using namespace std;
const int N = 100010;
int x, n, k, arr[N], l = 1, r, m, ans, cnt;
bool mp(int d)//根据 d 计算 cnt，并返回是否可行，cnt <= k 就是可行的
{cnt = 0;for (int i = 1; i < n; i++){cnt += (arr[i] - arr[i - 1] - 0.5) / d;if (cnt > k) return false;}return true;
}
int main()
{scanf("%d%d%d", &x, &n, &k);r = x;for (int i = 0; i < n; i++) scanf("%d", &arr[i]);while (l <= r){m = l + r >> 1;if (mp(m)) ans = m, r = m - 1;else l = m + 1;}printf("%d", ans);return 0;
}