19529 照明灯安装

### 详细分析

这个问题可以通过二分查找和贪心算法来解决。我们需要找到一个最大值,使得在这个最大值下,能够在给定的坐标上安装 `k` 个照明灯,并且相邻的照明灯之间的距离至少为这个最大值。

### 思路

1. **排序**:首先对给定的坐标进行排序(虽然题目保证了输入是有序的,但为了通用性,还是进行排序)。
2. **二分查找**:使用二分查找来确定最大距离。
3. **贪心算法**:在每次二分查找的过程中,使用贪心算法来验证是否可以在当前距离下安装 `k` 个照明灯。

### 伪代码

```plaintext
function canPlaceLamps(positions, n, k, distance):
    count = 1
    last_position = positions[0]
    for i from 1 to n:
        if positions[i] - last_position >= distance:
            count += 1
            last_position = positions[i]
        if count >= k:
            return true
    return false

function maxMinDistance(positions, n, k):
    sort(positions)
    left = 1
    right = positions[n-1] - positions[0]
    result = 0
    while left <= right:
        mid = (left + right) // 2
        if canPlaceLamps(positions, n, k, mid):
            result = mid
            left = mid + 1
        else:
            right = mid - 1
    return result
```

### C++代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool canPlaceLamps(const vector<int>& positions, int n, int k, int distance) {
    int count = 1;
    int last_position = positions[0];
    for (int i = 1; i < n; ++i) {
        if (positions[i] - last_position >= distance) {
            count++;
            last_position = positions[i];
        }
        if (count >= k) {
            return true;
        }
    }
    return false;
}

int maxMinDistance(vector<int>& positions, int n, int k) {
    sort(positions.begin(), positions.end());
    int left = 1;
    int right = positions[n - 1] - positions[0];
    int result = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canPlaceLamps(positions, n, k, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> positions(n);
    for (int i = 0; i < n; ++i) {
        cin >> positions[i];
    }
    cout << maxMinDistance(positions, n, k) << endl;
    return 0;
}

### 结论

通过上述代码,我们可以计算出在给定的坐标上安装 `k` 个照明灯,使得相邻的照明灯之间的最小距离最大。代码使用二分查找和贪心算法,确保了计算的准确性和效率。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/871470.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

arthas源码刨析:启动 (1)

文章目录 arthas-bootBootstrap Created with Raphal 2.3.0 开始 检查监听端口 jps 列表java应用 下载 lib 依赖 功能移交给 arthas-core 结束 arthas-boot 该module 的代码只有3个类&#xff1a; Bootstrap 启动类 Bootstrap &#xff0c;开头的注解就是 alibaba 的 cli 中…

凡图公益行:凡图家庭教育以行动筑梦,点亮孩子心中的光芒

在教育的路上&#xff0c;每一步都承载着未来的希望&#xff0c;凡图(山东)教育科技集团有限公司一直致力于为每一个孩子及家庭提供最优质的心理咨询服务。 在这样的背景下&#xff0c;凡图家庭教育以独特的使命感和责任感&#xff0c;成为了众多家庭信赖的伙伴。 也因此成为…

阿里Qwen2开源大模型本地部署及调试全攻略

阿里Qwen2开源大模型本地部署及调试全攻略 #Qwen2系列大模型性能卓越&#xff0c;超越业界知名模型。开源后受到AI开发者关注&#xff0c;支持多种语言&#xff0c;提升多语言理解。在预训练和微调上优化&#xff0c;实现智能水平提升。Qwen2系列模型在各项能力上均领先&#…

glibc 2.24 下 IO_FILE 的利用

文章目录 glibc 2.24 下 IO_FILE 的利用介绍&#xff1a;新的利用技术fileno 与缓冲区的相关利用实例&#xff1a;1. _IO_str_jumps -> overflow实例&#xff1a; 2. _IO_str_jumps -> finish实例: 最后拓展一下上一篇博客house of orange题目的做法: glibc 2.24 下 IO_F…

怎么对前端的一些按钮做一个权限校验

在一般情况下,我们需要对一些按钮做一个权限校验,来保证只有有权限的用户才能看到 1.创建一个js文件,来写我们的全局方法 我的方法是这样的 import Vue from vue;Vue.mixin({methods:{hasAuth(perm) {var authority this.$store.state.menu.permList;if (authority.indexOf(…

又搞到两款海外AI神器,确实强!

哈喽&#xff0c;各位小伙伴们好&#xff0c;我是给大家带来各类黑科技与前沿资讯的小武。 今天给大家安利两款海外AI神器&#xff0c;均已解除专业版限制&#xff0c;免翻&#xff0c;即可使用AI图片/视频修复(清晰度增强)、AI图片/视频一键抠图、AI证件照、美颜相机等强大功…

STM32的GPIO

GPIO基本控制 GPIO(General-Purpose input/output,通用输入/输出接口) 用于感知外部信号&#xff08;输入模式&#xff09;和控制外部设备&#xff08;输出模式&#xff09; 简单模块&#xff1a;LED,按键&#xff0c;蜂鸣器&#xff0c;温度传感器&#xff0c;使用一个GPIO…

安装MySQL入门基础指令

一.安装MySQL(以5.7版本为例) 1.一路默认安装&#xff0c;截图供大家参考 修改自己window安装名字即可 2.配置环境变量 C:\Program Files\MySQL\MySQL Server 5.7\bin 写入系统环境变量即可在window窗口使用其服务了 3.登录MySQL服务 进入控制台输入命令 mysql -u root …

MySQL InnoDB引擎四大特性ACID实现方案分析

文章目录 概要InnoDb引擎ACID模型的实现方案小结 概要 对于Mysql&#xff0c;事物的支撑并不依赖于Server层&#xff0c;不同的存储引擎对于事物的支持也不一样&#xff0c;对于我们常用的InnoDB引擎&#xff0c;其提供了一套基于【ACID模型】的事物完整的解决方案。为什么MyIS…

初识C++:开启C++之旅

目录 1.C的第一个程序 2.namesapce命名空间域 2.1namespace的意义 2.2.2namespace的定义 2.3命名空间的使用 3.C输入/输出 4.缺省参数 5.函数重载 6.引用 6.1引用的特性 6.2引用的使用 1.C的第一个程序 c版本&#xff1a; #include<iostream>using std::cout…

线性代数:每日一题1/特征值与相似对角化

设A, B 为二阶矩阵&#xff0c;且 AB BA , 则“A有两个不相等的特征值”是“B可对角化"的&#xff08;&#xff09; A. 充分必要条件 B. 充分不必要条件 C.必要不充分条件 D.既不充分也不必要条件 知识点&#xff1a; 特征向量与特征值的关系 相似矩阵的定义和性质 n阶…

计算机网络之TCP序号,确认序号和报文传输时间

开篇提示 本篇适合于了解基础知识&#xff0c;进行扩展提高的使用&#xff0c;附带考研习题以及解析。 TCP序号和确认序号的区别 TCP首部中有序号和确认序号&#xff0c;他们都是4个字节&#xff08;4B&#xff09;&#xff0c;且在数据传输中有很重要的意义&#xff0c;那么两…

【后端记录】修复MySql的错误修改的数据记录【binlog修复】

前言 今天入门后端的时候&#xff0c;不小心改了非预期的数据&#xff0c;因为还没学到事务&#xff0c;所以恢复数据还比较麻烦&#xff0c;站在巨人的肩膀上还是解决了&#xff0c;原文连接在下面 https://blog.csdn.net/qq_42874315/article/details/140480570 解决办法 原…

Spring核心思想讲解之控制反转(IOC)

控制反转概述 控制反转实现方式 XML方式 方式一 方式二 方式三 注解方式 第一步 第二步 第三步 依赖注入&#xff08;DI&#xff09;实现方式 XML方式 手动注入 set注入 构造器注入 自动注入 set注入 构造方法注入 注解方式 方式一&#xff1a; 方式二&…

用excel内容批量建立文件夹

建文件夹是电脑操作过程中比较常见的&#xff0c;但是用EXCEL内容批量建文件夹&#xff0c;这似乎不相关的两个操作&#xff0c;那么怎么实现这样的一个功能&#xff0c;我们需要用到专门的软件进行关联&#xff0c;推荐&#xff1a;可易文件夹批量生成器&#xff0c;这个软件有…

RCE编码绕过--php://filter妙用

目录 代码 如何绕过 payload构造 代码 <?php $content <?php exit; ?>; $content . $_POST[txt]; file_put_contents($_POST[filename],$content); 当你想要输入代码的时候前面会有<?php exit;?>;&#xff0c;代码没有办法执行下去&#xff0c;所以…

Linux驱动学习之点灯(四,linux2.6)

上篇最后的第二种点灯方法年代比较久远&#xff0c;register_chrdev&#xff08;&#xff09;这个函数一下申请了255个设备号&#xff0c;不建议使用 如下图 下图的函数在linux2.6里是上图函数的升级版&#xff0c;不过他是静态分配&#xff0c;后续还得添加到cdev里 从上图函…

【自动驾驶】控制算法(三)轮胎侧偏与车辆动力学模型

写在前面&#xff1a; &#x1f31f; 欢迎光临 清流君 的博客小天地&#xff0c;这里是我分享技术与心得的温馨角落。&#x1f4dd; 个人主页&#xff1a;清流君_CSDN博客&#xff0c;期待与您一同探索 移动机器人 领域的无限可能。 &#x1f50d; 本文系 清流君 原创之作&…

回收站的文件删除了怎么恢复?4个技巧轻松找回文件!

在日常使用电脑的过程中&#xff0c;回收站作为我们删除文件的临时存放地&#xff0c;扮演着重要的角色。然而&#xff0c;有时我们可能会不小心从回收站中删除了重要文件&#xff0c;导致数据丢失。面对这种情况&#xff0c;许多用户会感到焦虑和无助。但别担心&#xff0c;本…

白酒与素食:健康与美味的双重享受

在美食的世界里&#xff0c;白酒与素食的搭配仿佛是一场跨界的盛宴。豪迈白酒&#xff08;HOMANLISM&#xff09;的醇香与精致素食的清新&#xff0c;在不经意间交织出了一幅美妙的画卷&#xff0c;让人在品味中感受到健康与美味的双重享受。 素食&#xff0c;以其清淡、自然的…