专栏文章

P3853 [TJOI2007] 路标设置

EEverything_
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip6ek48
此快照首次捕获于
2025/12/03 06:55
3 个月前
此快照最后确认于
2025/12/03 06:55
3 个月前
查看原文

读题

我们要求出最小的空旷指数，“空旷指数”指的是公路上相邻路标的最大距离，我们就来分析一下样例：
Input:\tt{Input:}
LATEX
101 2 1
0 101
Output:\tt Output:
LATEX
51
也就是在 5050 的位置上，则此时的“空旷指数”就为 max(50−(0−1),101−(51−1))=51\tt{max}(50-(0-1),101-(51-1)) = 51 但是如果我们 放在 5151 位置时，那么此时我们的“空旷指数”就是 max(51−(0−1),101−(51−1))=52\tt{max}(51 - (0 - 1), 101 - (51 - 1)) = 52 ，放在 4949 也同理，那么我们就发现：
在两个路障之间，我们要放置若干个路障我们就要使两两之间路障的距离尽量相等。

那我们就可以写代码了

相信要写这一道题的同学应该都已经对二分算法已经有了一定的理解与联系了，那我们就不过多介绍二分了。
因为题面要求的数是最小的“空旷指数”，所以我们显而易见二分枚举“空旷指数”。
CPP
#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int maxn = 10000005;
LL m, n, k, a[maxn], mid, l, r;
bool check(LL mid)
{
	LL s = a[1], w = 0;
	for(int i = 2; i <= n; i++)
	{
		while(a[i] - s > mid) 
		{
			w++;
			s = s + mid;
		}
		if(a[i] - s <= mid)
			s = a[i];
	}
	return w <= k;
}

int main()
{
	cin >> m >> n >> k;
	r = m + 1;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	while(l + 1 < r)
	{
		mid = l + r >> 1;
		if(check(mid))
			r = mid;
		else
			l = mid;
	}
	cout << r;
	return 0;
}

PS*

关于 check函数\tt{check} 函数 我的变量 s\tt s 表示上一个路障的位置，w\tt w 表示此时所需的路障数量。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...