【洛谷】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

相关文章
|
6月前
【每日一题Day312】LC2240买钢笔和铅笔的方案数 | 完全背包 数学
【每日一题Day312】LC2240买钢笔和铅笔的方案数 | 完全背包 数学
56 0
|
5月前
【洛谷 P2669】[NOIP2015 普及组] 金币 题解(循环)
`NOIP2015`普及组题目,骑士按周期领金币:第一天1枚,随后$n$天每天$n$枚,然后$n+1$天每天$n+1$枚。给定天数$k$,求总金币数。输入$k$,输出金币总数。样例输入6,输出14;输入1000,输出29820。代码使用循环和变量控制周期,累计金币数。
90 0
|
5月前
【洛谷 P1909】[NOIP2016 普及组] 买铅笔 题解(打擂台法)
**摘要:** P老师需买$n$支铅笔作礼物,商店有3种包装(数量、价格不等),不能拆包。目标是最少花费。输入包括$n$和每种包装的详情,输出最小花费。样例展示最优选择过程。代码使用打擂台法求解,读入$n$和包装信息,计算每种包装的最小花费,取最小值输出。
50 0
|
5月前
|
C++
【洛谷 P1059】[NOIP2006 普及组] 明明的随机数 题解(集合)
**NOIP2006普及组题目**,明明需生成不重复的1-1000间随机整数,输入含两行:第一行是整数N(≤100),第二行是N个随机数。输出两行,第一行是唯一数的个数M,第二行是排序后的唯一数。示例:输入10个数含重复,输出8个不同数排序后结果。解题方法:利用C++的`set`进行去重和排序。
54 0
|
5月前
|
机器学习/深度学习 存储
【洛谷 P1028】[NOIP2001 普及组] 数的计算 题解(递归)
**NOIP2001普及组数的计算**:给定自然数\( n \),构造数列,新数不超过序列最后一项一半。求合法数列个数。输入\( n \)(\(1 \leq n \leq 10^3\))。样例:输入6,输出6。递归解决,代码中定义函数`f`实现递归计算,总和存储在`cnt`中,最后输出。
48 0
|
5月前
【洛谷 P1618】三连击(升级版)题解(循环枚举+全排列)
该编程题目要求将数字1到9分为三组,形成三个三位数,使得这三个数成比例A:B:C。输入为A、B、C的值,输出符合条件的三位数组合,按首个数字升序排列。样例输入为1 2 3,输出多组解。代码使用全排列遍历数字,检查比例关系。若无解,则输出&quot;No!!!&quot;。
45 0
|
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代码略。
38 0
|
5月前
【洛谷 P1002】[NOIP2002 普及组] 过河卒 题解(递归+记忆化搜索)
`NOIP2002`普及组的过河卒问题是一个棋盘路径计数挑战。卒从$(0,0)$出发到$(n,m)$,只能向下或向右移动,马在$(c1,c2)$固定,控制某些点。任务是计算不受马阻挡的路径数。输入是目标和马的位置,输出是路径总数。使用动态规划和记忆化搜索避免重复计算,样例输入$(6,6,3,3)$输出$6$。代码中定义了$f(x,y)$计算$(x,y)$处的路径数,利用边界条件和递推关系计算。
57 0
|
5月前
|
Java
P9242 [蓝桥杯 2023 省 B] 接龙数列JAVA,边权为1的最短路问题,洛谷P9242 [蓝桥杯 2023 省 B] 接龙数列​编辑力扣1926.迷宫离入口最近的出口力扣433.
P9242 [蓝桥杯 2023 省 B] 接龙数列JAVA,边权为1的最短路问题,洛谷P9242 [蓝桥杯 2023 省 B] 接龙数列​编辑力扣1926.迷宫离入口最近的出口力扣433.