杭州网站推广与优化,网站建设 行业资讯,图片站手机网站怎么做的,产品网页设计多少钱原题链接#xff1a;https://www.luogu.com.cn/problem/P3853
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
整体思路#xff1a;二分答案
由题意知#xff0c;公路上相邻路标的最大距离定义为该公路的“空旷指数”。在公路上增设一些路标…原题链接https://www.luogu.com.cn/problem/P3853
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
整体思路二分答案
由题意知公路上相邻路标的最大距离定义为该公路的“空旷指数”。在公路上增设一些路标使得公路的“空旷指数”最小。也就是满足最大值最小。我们就自然想到可以二分答案。
定义三个变量Lnk分别表示公路的长度原有路标的数量以及最多可增设的路标数量。开一个数组a数组的第i个元素a[i]表示原有路标与起点的距离。
我们这里又开了一个差值数组s令s[i]a[i]-a[i-1]这样就可以用数组s表示原有的两个相邻路标的距离。
令左边界l0右边界rL。
套用二分模板mid(lr)1。主要就是要写一个check()函数设check()函数的形参为x将mid传入x。我们定义一个cnt变量用于记录新增的路标数量遍历s[i]数组如果s[i]x我们就要新增一个路标(cnt)同时我们判断剩余部分s[i]-x的长度和x的关系如果剩余部分的长度比x大我们就继续插路标cnt直到numx。
for循环结束后我们判断一下cnt新增路标数量和k最多可增设的路标数量如果cntkreturn true。否则return false。
3. 代码实现
#includebits/stdc.h
using namespace std;
#define ll long long
const int N 100010;
ll a[N], s[N], L, n, k, maxx;bool check(int x) {ll cnt 0;for (int i 1; i n; i) {if (s[i] x) {cnt;int num s[i] - x;while (num x) {cnt;num - x;}}}if (cnt k) return true;else return false;
}int main() {cin L n k;for (int i 1; i n; i) {cin a[i];s[i] a[i] - a[i - 1];}int l 0, r L;while (l 1 r) {int mid (l r) 1;if (check(mid)) r mid;else l mid;}cout r endl;return 0;
}
