【洛谷】P3853 路标设置

简介: 洛谷P3853 路标设置

1. 题目描述

image.png

2. 思路分析

整体思路:二分答案

由题意知,公路上相邻路标的最大距离定义为该公路的“空旷指数”。在公路上增设一些路标,使得公路的“空旷指数”最小。也就是满足最大值最小。我们就自然想到可以二分答案。

定义三个变量L,n,k分别表示公路的长度,原有路标的数量,以及最多可增设的路标数量。开一个数组a,数组的第i个元素a[i]表示原有路标与起点的距离。

我们这里又开了一个差值数组s,令s[i]=a[i]-a[i-1],这样就可以用数组s表示原有的两个相邻路标的距离。

令左边界l=0,右边界r=L。

套用二分模板,mid=(l+r)>>1。主要就是要写一个check()函数,设check()函数的形参为x,将mid传入x。我们定义一个cnt变量用于记录新增的路标数量,遍历s[i]数组,如果s[i]>x,我们就要新增一个路标(cnt++),同时我们判断剩余部分(s[i]-x)的长度和x的关系,如果剩余部分的长度比x大,我们就继续插路标(cnt++),直到num<=x。

for循环结束后,我们判断一下cnt(新增路标数量)和k(最多可增设的路标数量),如果cnt<=k,return true。否则return false。

3. 代码实现

#include<bits/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;
}

image.png

相关文章
|
5月前
|
算法
【洛谷 P1003】[NOIP2011 提高组] 铺地毯 题解(数组+贪心算法)
**NOIP2011 提高组问题:铺地毯** 在第一象限的颁奖典礼场地,有$n$张地毯按编号顺序铺设。需找出覆盖特定点$(x, y)$的最上方地毯编号。输入包括地毯坐标和点坐标,输出地毯编号或-1表示未覆盖。 样例:给定3张地毯,点$(2,2)$被第3张地毯覆盖,输出3;另一样例点$(4,5)$未被覆盖,输出-1。 $30\%$数据$n\leq2$,$50\%$数据坐标$\leq100$,$100\%$数据$n\leq10^4$,坐标$\leq10^5$。 解决方法:从下到上遍历地毯,更新覆盖点的地毯编号。 AC代码略。
49 0
|
算法 Cloud Native
【刷题日记】513. 找树左下角的值
本次刷题日记的第 74 篇,力扣题为:513. 找树左下角的值 ,中等
[算法刷题题解笔记] 洛谷 P1003 [NOIP2011 提高组] 铺地毯 [枚举]
[算法刷题题解笔记] 洛谷 P1003 [NOIP2011 提高组] 铺地毯 [枚举]
[算法刷题题解笔记] 洛谷 P1008 [NOIP1998 普及组] 三连击 [枚举|模拟]
[算法刷题题解笔记] 洛谷 P1008 [NOIP1998 普及组] 三连击 [枚举|模拟]
|
Java Python
leetcode每日一题.面试题62:圆圈中最后剩下的数字
leetcode每日一题.面试题62:圆圈中最后剩下的数字
67 0
|
JavaScript 索引
leetcode_18. 四数之和,n 数之和完结篇
题目链接:18. 四数之和 这个人已经靠 n 数之和水了好几篇文章了,已经不想再水了 我之前写过好几篇的 nSum 相关的文章,在我的个人主页里面搜索可以发现有三篇相关的文章,当然看的人不多,但是还是决定要把这个类型题写完,也就是今天的终章 `nSum`
leetcode_18. 四数之和,n 数之和完结篇
|
存储
【蓝桥杯集训·每日一题】AcWing 1079. 叶子的颜色
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 树形DP
64 0
|
机器学习/深度学习
【蓝桥杯集训·每日一题】AcWing 3502. 不同路径数
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴
70 0