NOIP2015 推销员

这里如果按照距离来考虑就太复杂了,于是转化对象,考虑客户

证明:

假设我们选的疲劳值最大的前X个的最远的一个的距离为 S 1 S_{1} S1,那么可以知道,一定不会存在一个更优的方案,使得这个方案的最远的距离比 S 1 S_{1} S1要小

所以更优的方案的最远的距离肯定要比 S 1 S_{1} S1大,假设我们选择了一个比 S 1 S_{1} S1远的,距离为 S 2 S_{2} S2的住户作为这个方案的最远的住户,我们直接考虑在这个情形下的最优状态是什么。肯定是选择 X − 1 X-1 X1个住户,这些住户的距离小于 S 2 S_{2} S2,疲劳值尽可能大

那么肯定选择疲劳值前 X − 1 X-1 X1大的住户,就是最开始的方案去掉疲劳值最小的住户

插一句,这一道题目在做的时候,我从样例感觉出来了一个结论,就是 X X X的决策一定包含 X − 1 X-1 X1的决策,考虑多增加哪一个住户就可以了

从部分题解来看,这个想法也是正确的,但是不知道怎么证明

update 2024.7.21

哎,想到了转换对象,将客户排序了,但是没有想到这么做啊。。。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

(一)万字长文系列,redolog看这篇就够了 —— redolog的作用?写入方式是什么?什么是日志文件组?redolog的写入策略是怎样的?

导语 MySQL是一种广泛使用的开源关系型数据库管理系统,由瑞典公司MySQL AB开发,现由Oracle公司维护。它以其高性能、可靠性和易用性而著称,广泛应用于各种Web应用程序。MySQL支持多种操作系统,包括Windows、Linux和macOS&#xf…

Kafka Producer发送消息流程之分区器和数据收集器

文章目录 1. Partitioner分区器2. 自定义分区器3. RecordAccumulator数据收集器 1. Partitioner分区器 clients/src/main/java/org/apache/kafka/clients/producer/KafkaProducer.java,中doSend方法,记录了生产者将消息发送的流程,其中有一步…

【自动化测试】几种常见的自动化测试框架

在软件测试领域,自动化测试框架有很多,这里主要介绍几种常用的自动化测试框架。 1.pytest pytest 是 Python 的一种单元测试框架,与 Python 自带的 unittest 测试框架类似,但是比 unittest 框架使用起来更简洁,效率更高…

UDP详细总结

UDP协议特点 UDP是无连接的传输层协议; UDP使用尽最大努力交付,不保证可靠交付; UDP是面向报文的,对应用层交下来的报文,不合并,不拆分,保留原报文的边界; UDP没有拥塞控制&#…

[集成学习]基于python的Stacking分类模型的客户购买意愿分类预测

1 导入必要的库 import pandas as pd import numpy as np import missingno as msno import matplotlib.pyplot as plt from matplotlib import rcParams import seaborn as sns from sklearn.metrics import roc_curve, auc from sklearn.linear_model import LogisticRegres…

【C#】计算两条直线的交点坐标

问题描述 计算两条直线的交点坐标,可以理解为给定坐标P1、P2、P3、P4,形成两条线,返回这两条直线的交点坐标? 注意区分:这两条线是否垂直、是否平行。 代码实现 斜率解释 斜率是数学中的一个概念,特别是…

改变你对文本生成程序的误解!用C++标准库,MinGW情况下,写一个文本生成器(一种AI)

声明:我这个不是那种“文本生成器” 我之前见过那种“自动写作文”的程序,无非就是这样的文章: 文章写的只有主题,没有内容 我曾多次向我的朋友提问他们看没看过那种AI写作的代码,而给我的回复很简单:你弄那玩楞干哈?装*?那玩楞我见过,写的文章空有其表,没有其实;…

Java并发04之线程同步机制

文章目录 1 线程安全1.1 线程安全的变量1.2 Spring Bean1.3 如果保证线程安全 2 synchronized关键字2.1 Java对象头2.1.1 对象组成部分2.1.2 锁类型2.1.3 锁对象 2.2 synchronized底层实现2.2.1 无锁状态2.2.2 偏向锁状态2.2.3 轻量级锁状态2.2.4 重量级锁2.2.5 锁类型总结2.2.…

windows USB 设备驱动开发-编写 UCSI 客户端驱动程序

编写 UCSI 客户端驱动程序 USB Type-C 连接or 系统软件接口(UCSI)驱动程序充当带有嵌入式控制器(EC)的 USB Type-C 系统的控制器驱动程序。 如果实现平台策略管理器(PPM)的系统,如 UCSI 规范中…

国产化低功耗HDMI转VGA方案,大量出货产品,广泛应用在显示器以及广告机产品

芯片描述: 兼具高性能和低成本效益的优点,是一款可以将高清视频 HDMI1.4 数字信号转换成 VGA 模拟信号输出的芯片。不需要提供外部电源,ICNM7301 就可以在正常模式下使用;ICNM7301 广 泛适用于各种市场系统和显示应用体系&#x…

LabVIEW异步和同步通信详细分析及比较

1. 基本原理 异步通信: 原理:异步通信(Asynchronous Communication)是一种数据传输方式,其中数据发送和接收操作在独立的时间进行,不需要在特定时刻对齐。发送方在任何时刻可以发送数据,而接收…

2024年广东省安全员B证第四批(项目负责人)证模拟考试题库及广东省安全员B证第四批(项目负责人)理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年广东省安全员B证第四批(项目负责人)证模拟考试题库及广东省安全员B证第四批(项目负责人)理论考试试题是由安全生产模拟考试一点通提供,广东省安全员B证…

手持式气象站:便携科技,掌握微观气象的利器

手持式气象站,顾名思义,是一种可以随身携带的气象监测设备。它小巧轻便,通常配备有温度、湿度、风速、风向、气压等多种传感器,能够实时测量并显示各种气象参数。不仅如此,它还具有数据存储、数据传输、远程控制等多种…

kafka开启kerberos和ACL

作者:恩慈 一、部署kafka-KB包 1.上传软件包 依次点击 部署中心----部署组件----上传软件包 选择需要升级的kafka版本并点击确定 2.部署kafka 依次点击部署中心----部署组件----物理/虚拟机部署----选择集群----下一步 选择手动部署-…

MongoDB自学笔记(四)

一、前文回顾 上一篇文章中我们学习了MongoDB中的更新方法&#xff0c;也学了一部分操作符。今天我们将学习最后一个操作“删除”。 二、删除 原始数据如下&#xff1a; 1、deleteOne 语法&#xff1a;db.collection.deleteOne(< query >,< options >) 具体参…

学生信息管理系统-可视化-科目管理CRUD代码生成器

学生管理系统中的科目管理是一个重要的组成部分&#xff0c;它负责维护和管理学校中所有的教学科目信息。 可视化快速界面生成CRUD界面&#xff0c;API通过代码生成器生成器生成。 新增数据库表 拷贝demo_table修改为clazz_kemu表 修改表结构 其中包括一个自增ID字段&#x…

在虚拟机 CentOS7 环境下安装 MySQL5.7 数据库

配置目标 在虚拟机的 Linux CentOS7 环境下安装 MySQL5.7 版数据库&#xff0c;并能从宿主机 Windows 系统连接该数据库&#xff08;默认端口&#xff1a;3306&#xff09;。 1. 准备工作 WMware 虚拟机&#xff1a;VMware Workstation 16 ProCentOS7 镜像&#xff1a;CentO…

Java面试题--JVM大厂篇之深入解析JVM中的Serial GC:工作原理与代际区别

目录 引言&#xff1a; 正文&#xff1a; 一、Serial GC工作原理 年轻代垃圾回收&#xff08;Minor GC&#xff09;&#xff1a; 老年代垃圾回收&#xff08;Major GC或Full GC&#xff09;&#xff1a; 二、年轻代和老年代的区别 年轻代&#xff08;Young Generation&a…

redis其他类型和配置文件

很多博客只讲了五大基本类型&#xff0c;确实&#xff0c;是最常用的&#xff0c;而且百分之九十的程序员对于Redis只限于了解String这种最常用的。但是我个人认为&#xff0c;既然Redis官方提供了其他的数据类型&#xff0c;肯定是有相应的考量的&#xff0c;在某些特殊的业务…

【C++】——new和delete

文章目录 热身试题C中的内存管理new与delete对于内置类型的操作new与delete对于自定义类型的操作 malloc/free和new/delete的区别 热身试题 int globalVar 1; static int staticGlobalVar 1; void Test() {static int staticVar 1;int localVar 1;int num1[10] { 1, 2, 3…