信息学奥赛一本通 1422:【例题1】活动安排
【题目链接】
ybt 1422:【例题1】活动安排
【题目考点】
1. 贪心
【解题思路】
该题属于区间选点问题,ybt 1324:【例6.6】整数区间 是给定一些区间,选择一些点使得每个区间范围内至少有1个点。
本题为:给定一些区间,选择一些点使得每个区间范围内至少有给定数量的点。
本题中,每个地块可以看作数轴上的一个点,“B和E之间最少种T棵树”,指的是在区间[B, E]中至少选择T个点。
贪心选择:对每个区间,如果还需要选点,则尽量从区间右侧选点。
所有区间按照右端点 E E E从小到大排序,排序后第i区间范围为 [ B i , E i ] [B_i, E_i] [Bi,Ei],其中需要至少选择 T i T_i Ti个点。
贪心选择的具体解释:
- 如果该区间中已经选择点的数量大于等于 T i T_i Ti,则不需要再选点。
- 如果该区间中已经选择点的数量小于 T i T_i Ti,则从 E i E_i Ei到 B i B_i Bi从大到小遍历每个点,遇到未选择的点就选择该点,直到选够 T i T_i Ti个点。
贪心选择性质的证明:
- 证明存在最优解包含第一次的贪心选择
第一次的贪心选择为:在 [ B 1 , E 1 ] [B_1,E_1] [B1,E1]中选择区间 [ E 1 − T 1 + 1 , E 1 ] [E_1-T_1+1, E_1] [E1−T1+1,E1]中的整数点,共 T 1 T_1 T1个点。
反证法:假设所有最优解都不包含第一次的贪心选择
也就是说在 [ B 1 , E 1 − T 1 ] [B_1, E_1-T_1] [B1,E1−T1]选择了一些点,而 [ E 1 − T 1 + 1 , E 1 ] [E_1-T_1+1, E_1] [E1−T1+1,E1]中存在未被选择的点。设在 [ B 1 , E 1 − T 1 ] [B_1, E_1-T_1] [B1,E1−T1]中选择了点 G G G,而 [ E 1 − T 1 + 1 , E 1 ] [E_1-T_1+1, E_1] [E1−T1+1,E1]中点 F F F未被选择。
现在不选择点 G G G转而选择点 F F F,第2、第3等后面的区间中已选择的点可能会增加,也可能不变。每个区间的选点数量都满足要求,总选点数量不变。因此这样变换选择点后,此时的选点方案仍然是最优解。
将在 [ B 1 , E 1 − T 1 ] [B_1, E_1-T_1] [B1,E1−T1]中选择的所有点都去掉,转而在 [ E 1 − T 1 + 1 , E 1 ] [E_1-T_1+1, E_1] [E1−T1+1,E1]中选择相同数量的点,最后选择的点就是 [ E 1 − T 1 + 1 , E 1 ] [E_1-T_1+1, E_1] [E1−T1+1,E1]中的每个点,这也就是进行了贪心选择,这个包含了第一次贪心选择的解仍然是最优解。这与假设相悖,原命题得证。- 假设最优解包含前k次的贪心选择,证明存在最优解包含第k+1次的贪心选择:
证明过程与第1点的证明过程相似,不再赘述。
具体实现:
设vis数组,vis[i]表示第i点是否已被选择。
对于每个区间,先遍历整个区间,统计出已选点数量,也就是求出待选择点的数量。
- 如果待选择点的数量为0,就看下一个区间。
- 否则,从区间右端点开始,向前遍历,遇到未选择的点,就选择一个点,直到待选择点的数量为0。统计选点总数量,就是问题结果。
【题解代码】
解法1:贪心
#include<bits/stdc++.h>//贪心选择性质:按区间右端点升序排序,每个区间尽量选后面的数字
using namespace std;
struct Node
{int b, e, t;//[b, e]中选t个数
};
bool cmp(Node a, Node b)
{return a.e < b.e;
}
bool vis[30005];//vis[i]:点i是否已被选择
int main()
{Node a[5005];int n, m, ans = 0;//ans:总选点数量 cin >> n >> m;for(int i = 1; i <= m; ++i)cin >> a[i].b >> a[i].e >> a[i].t; sort(a+1, a+1+m, cmp);for(int i = 1; i <= m; ++i){for(int j = a[i].b; j <= a[i].e; ++j) if(vis[j] && --a[i].t <= 0)//a[i].t这里表示区间中还需要选择几个点break;if(a[i].t <= 0) continue;for(int j = a[i].e; j >= a[i].b; --j) if(!vis[j]){vis[j] = true;ans++;if(--a[i].t <= 0)break;}}cout << ans;return 0;
}
相关文章:
信息学奥赛一本通 1422:【例题1】活动安排
【题目链接】 ybt 1422:【例题1】活动安排 【题目考点】 1. 贪心 【解题思路】 该题属于区间选点问题,ybt 1324:【例6.6】整数区间 是给定一些区间,选择一些点使得每个区间范围内至少有1个点。 本题为:给定一些区…...
数据库、数据仓库、数据湖有什么不同
数据库、数据仓库和数据湖是三种不同的数据存储和管理技术,它们在用途、设计目标、数据处理方式以及适用场景上存在显著差异。以下将从多个角度详细说明它们之间的区别: 1. 数据结构与存储方式 数据库: 数据库主要用于存储结构化的数据&…...
llama.cpp LLM_CHAT_TEMPLATE_DEEPSEEK_3
llama.cpp LLM_CHAT_TEMPLATE_DEEPSEEK_3 1. LLAMA_VOCAB_PRE_TYPE_DEEPSEEK3_LLM2. static const std::map<std::string, llm_chat_template> LLM_CHAT_TEMPLATES3. LLM_CHAT_TEMPLATE_DEEPSEEK_3References 不宜吹捧中国大语言模型的同时,又去贬低美国大语言…...
深度学习的应用场景及常用技术
深度学习作为机器学习的一个重要分支,在众多领域都有广泛的应用,以下是一些主要的应用场景及常用技术。 1.应用场景 1. 计算机视觉 图像分类 描述:对图像中的内容进行分类,识别出图像中物体所属的类别。例如,在安防领…...
小程序项目-购物-首页与准备
前言 这一节讲一个购物项目 1. 项目介绍与项目文档 我们这里可以打开一个网址 https://applet-base-api-t.itheima.net/docs-uni-shop/index.htm 就可以查看对应的文档 2. 配置uni-app的开发环境 可以先打开这个的官网 https://uniapp.dcloud.net.cn/ 使用这个就可以发布到…...
网件r7000刷回原厂固件合集测评
《网件R7000路由器刷回原厂固件详解》 网件R7000是一款备受赞誉的高性能无线路由器,其强大的性能和可定制性吸引了许多高级用户。然而,有时候用户可能会尝试第三方固件以提升功能或优化网络性能,但这也可能导致一些问题,如系统不…...
微信登录模块封装
文章目录 1.资质申请2.combinations-wx-login-starter1.目录结构2.pom.xml 引入okhttp依赖3.WxLoginProperties.java 属性配置4.WxLoginUtil.java 后端通过 code 获取 access_token的工具类5.WxLoginAutoConfiguration.java 自动配置类6.spring.factories 激活自动配置类 3.com…...
[STM32 - 野火] - - - 固件库学习笔记 - - -十三.高级定时器
一、高级定时器简介 高级定时器的简介在前面一章已经介绍过,可以点击下面链接了解,在这里进行一些补充。 [STM32 - 野火] - - - 固件库学习笔记 - - -十二.基本定时器 1.1 功能简介 1、高级定时器可以向上/向下/两边计数,还独有一个重复计…...
后台管理系统通用页面抽离=>高阶组件+配置文件+hooks
目录结构 配置文件和通用页面组件 content.config.ts const contentConfig {pageName: "role",header: {title: "角色列表",btnText: "新建角色"},propsList: [{ type: "selection", label: "选择", width: "80px&q…...
8.原型模式(Prototype)
动机 在软件系统中,经常面临着某些结构复杂的对象的创建工作;由于需求的变化,这些对象经常面临着剧烈的变化,但是它们却拥有比较稳定一致的接口。 之前的工厂方法和抽象工厂将抽象基类和具体的实现分开。原型模式也差不多&#…...
Python-基于PyQt5,pdf2docx,pathlib的PDF转Word工具(专业版)
前言:日常生活中,我们常常会跟WPS Office打交道。作表格,写报告,写PPT......可以说,我们的生活已经离不开WPS Office了。与此同时,我们在这个过程中也会遇到各种各样的技术阻碍,例如部分软件的PDF转Word需要收取额外费用等。那么,可不可以自己开发一个小工具来实现PDF转…...
13 尺寸结构模块(size.rs)
一、size.rs源码 // Copyright 2013 The Servo Project Developers. See the COPYRIGHT // file at the top-level directory of this distribution. // // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or // http://www.apache.org/licenses/LICENSE…...
STM32单片机学习记录(2.2)
一、STM32 13.1 - PWR简介 1. PWR(Power Control)电源控制 (1)PWR负责管理STM32内部的电源供电部分,可以实现可编程电压监测器和低功耗模式的功能; (2)可编程电压监测器(…...
CSS 样式化表格:从基础到高级技巧
CSS 样式化表格:从基础到高级技巧 1. 典型的 HTML 表格结构2. 为表格添加样式2.1 间距和布局2.2 简单的排版2.3 图形和颜色2.4 斑马条纹2.5 样式化标题 3. 完整的示例代码4. 总结 在网页设计中,表格是展示数据的常见方式。然而,默认的表格样式…...
【python】tkinter实现音乐播放器(源码+音频文件)【独一无二】
👉博__主👈:米码收割机 👉技__能👈:C/Python语言 👉专__注👈:专注主流机器人、人工智能等相关领域的开发、测试技术。 【python】tkinter实现音乐播放器(源码…...
javascript常用函数大全
javascript函数一共可分为五类: •常规函数 •数组函数 •日期函数 •数学函数 •字符串函数 1.常规函数 javascript常规函数包括以下9个函数: (1)alert函数:显示一个警告对话框,包括一个OK按钮。 (2)confirm函数:显…...
C#属性和字段(访问修饰符)
不同点逻辑性/灵活性存储性访问性使用范围安全性属性(Property)源于字段,对字段的扩展,逻辑字段并不占用实际的内存可以被其他类访问对接收的数据范围做限定,外部使用增加了数据的安全性字段(Field)不经过逻辑处理占用内存的空间及位置大部分字段不能直接被访问内存使用不安全 …...
DeepSeek为什么超越了OpenAI?从“存在主义之问”看AI的觉醒
悉尼大学学者Teodor Mitew向DeepSeek提出的问题,在推特上掀起了一场关于AI与人类意识的大讨论。当被问及"你最想问人类什么问题"时,DeepSeek的回答直指人类存在的本质:"如果意识是进化的偶然,宇宙没有内在的意义&a…...
langchain基础(二)
一、输出解析器(Output Parser) 作用:(1)让模型按照指定的格式输出; (2)解析模型输出,提取所需的信息 1、逗号分隔列表 CommaSeparatedListOutputParser:…...
数据库安全管理中的权限控制:保护数据资产的关键措施
title: 数据库安全管理中的权限控制:保护数据资产的关键措施 date: 2025/2/2 updated: 2025/2/2 author: cmdragon excerpt: 在信息化迅速发展的今天,数据库作为关键的数据存储和管理中心,已经成为了企业营运和决策的核心所在。然而,伴随着数据规模的不断扩大和数据价值…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
