信息学奥赛一本通 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: 在信息化迅速发展的今天,数据库作为关键的数据存储和管理中心,已经成为了企业营运和决策的核心所在。然而,伴随着数据规模的不断扩大和数据价值…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
TJCTF 2025
还以为是天津的。这个比较容易,虽然绕了点弯,可还是把CP AK了,不过我会的别人也会,还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...
大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程
基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...
ubuntu中安装conda的后遗症
缘由: 在编译rk3588的sdk时,遇到编译buildroot失败,提示如下: 提示缺失expect,但是实测相关工具是在的,如下显示: 然后查找借助各个ai工具,重新安装相关的工具,依然无解。 解决&am…...
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑 在电子商务领域,转化率与网站性能是决定商业成败的核心指标。今天,我们将深入解析不同类型电商平台的转化率基准,探讨页面加载速度对用户行为的…...
