当前位置: 首页 > news >正文

信息学奥赛一本通 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个点。

贪心选择性质的证明:

  1. 证明存在最优解包含第一次的贪心选择
    第一次的贪心选择为:在 [ B 1 , E 1 ] [B_1,E_1] [B1,E1]中选择区间 [ E 1 − T 1 + 1 , E 1 ] [E_1-T_1+1, E_1] [E1T1+1,E1]中的整数点,共 T 1 T_1 T1个点。
    反证法:假设所有最优解都不包含第一次的贪心选择
    也就是说在 [ B 1 , E 1 − T 1 ] [B_1, E_1-T_1] [B1,E1T1]选择了一些点,而 [ E 1 − T 1 + 1 , E 1 ] [E_1-T_1+1, E_1] [E1T1+1,E1]中存在未被选择的点。设在 [ B 1 , E 1 − T 1 ] [B_1, E_1-T_1] [B1,E1T1]中选择了点 G G G,而 [ E 1 − T 1 + 1 , E 1 ] [E_1-T_1+1, E_1] [E1T1+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,E1T1]中选择的所有点都去掉,转而在 [ E 1 − T 1 + 1 , E 1 ] [E_1-T_1+1, E_1] [E1T1+1,E1]中选择相同数量的点,最后选择的点就是 [ E 1 − T 1 + 1 , E 1 ] [E_1-T_1+1, E_1] [E1T1+1,E1]中的每个点,这也就是进行了贪心选择,这个包含了第一次贪心选择的解仍然是最优解。这与假设相悖,原命题得证。
  2. 假设最优解包含前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&#xff1a;【例题1】活动安排 【题目考点】 1. 贪心 【解题思路】 该题属于区间选点问题&#xff0c;ybt 1324&#xff1a;【例6.6】整数区间 是给定一些区间&#xff0c;选择一些点使得每个区间范围内至少有1个点。 本题为&#xff1a;给定一些区…...

数据库、数据仓库、数据湖有什么不同

数据库、数据仓库和数据湖是三种不同的数据存储和管理技术&#xff0c;它们在用途、设计目标、数据处理方式以及适用场景上存在显著差异。以下将从多个角度详细说明它们之间的区别&#xff1a; 1. 数据结构与存储方式 数据库&#xff1a; 数据库主要用于存储结构化的数据&…...

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 不宜吹捧中国大语言模型的同时&#xff0c;又去贬低美国大语言…...

深度学习的应用场景及常用技术

深度学习作为机器学习的一个重要分支&#xff0c;在众多领域都有广泛的应用&#xff0c;以下是一些主要的应用场景及常用技术。 1.应用场景 1. 计算机视觉 图像分类 描述&#xff1a;对图像中的内容进行分类&#xff0c;识别出图像中物体所属的类别。例如&#xff0c;在安防领…...

小程序项目-购物-首页与准备

前言 这一节讲一个购物项目 1. 项目介绍与项目文档 我们这里可以打开一个网址 https://applet-base-api-t.itheima.net/docs-uni-shop/index.htm 就可以查看对应的文档 2. 配置uni-app的开发环境 可以先打开这个的官网 https://uniapp.dcloud.net.cn/ 使用这个就可以发布到…...

网件r7000刷回原厂固件合集测评

《网件R7000路由器刷回原厂固件详解》 网件R7000是一款备受赞誉的高性能无线路由器&#xff0c;其强大的性能和可定制性吸引了许多高级用户。然而&#xff0c;有时候用户可能会尝试第三方固件以提升功能或优化网络性能&#xff0c;但这也可能导致一些问题&#xff0c;如系统不…...

微信登录模块封装

文章目录 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 - 野火] - - - 固件库学习笔记 - - -十三.高级定时器

一、高级定时器简介 高级定时器的简介在前面一章已经介绍过&#xff0c;可以点击下面链接了解&#xff0c;在这里进行一些补充。 [STM32 - 野火] - - - 固件库学习笔记 - - -十二.基本定时器 1.1 功能简介 1、高级定时器可以向上/向下/两边计数&#xff0c;还独有一个重复计…...

后台管理系统通用页面抽离=>高阶组件+配置文件+hooks

目录结构 配置文件和通用页面组件 content.config.ts const contentConfig {pageName: "role",header: {title: "角色列表",btnText: "新建角色"},propsList: [{ type: "selection", label: "选择", width: "80px&q…...

8.原型模式(Prototype)

动机 在软件系统中&#xff0c;经常面临着某些结构复杂的对象的创建工作&#xff1b;由于需求的变化&#xff0c;这些对象经常面临着剧烈的变化&#xff0c;但是它们却拥有比较稳定一致的接口。 之前的工厂方法和抽象工厂将抽象基类和具体的实现分开。原型模式也差不多&#…...

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&#xff08;Power Control&#xff09;电源控制 &#xff08;1&#xff09;PWR负责管理STM32内部的电源供电部分&#xff0c;可以实现可编程电压监测器和低功耗模式的功能&#xff1b; &#xff08;2&#xff09;可编程电压监测器&#xff08;…...

CSS 样式化表格:从基础到高级技巧

CSS 样式化表格&#xff1a;从基础到高级技巧 1. 典型的 HTML 表格结构2. 为表格添加样式2.1 间距和布局2.2 简单的排版2.3 图形和颜色2.4 斑马条纹2.5 样式化标题 3. 完整的示例代码4. 总结 在网页设计中&#xff0c;表格是展示数据的常见方式。然而&#xff0c;默认的表格样式…...

【python】tkinter实现音乐播放器(源码+音频文件)【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;专__注&#x1f448;&#xff1a;专注主流机器人、人工智能等相关领域的开发、测试技术。 【python】tkinter实现音乐播放器&#xff08;源码…...

javascript常用函数大全

javascript函数一共可分为五类&#xff1a; •常规函数 •数组函数 •日期函数 •数学函数 •字符串函数 1.常规函数 javascript常规函数包括以下9个函数&#xff1a; (1)alert函数&#xff1a;显示一个警告对话框&#xff0c;包括一个OK按钮。 (2)confirm函数&#xff1a;显…...

C#属性和字段(访问修饰符)

不同点逻辑性/灵活性存储性访问性使用范围安全性属性(Property)源于字段,对字段的扩展,逻辑字段并不占用实际的内存可以被其他类访问对接收的数据范围做限定,外部使用增加了数据的安全性字段(Field)不经过逻辑处理占用内存的空间及位置大部分字段不能直接被访问内存使用不安全 …...

DeepSeek为什么超越了OpenAI?从“存在主义之问”看AI的觉醒

悉尼大学学者Teodor Mitew向DeepSeek提出的问题&#xff0c;在推特上掀起了一场关于AI与人类意识的大讨论。当被问及"你最想问人类什么问题"时&#xff0c;DeepSeek的回答直指人类存在的本质&#xff1a;"如果意识是进化的偶然&#xff0c;宇宙没有内在的意义&a…...

langchain基础(二)

一、输出解析器&#xff08;Output Parser&#xff09; 作用&#xff1a;&#xff08;1&#xff09;让模型按照指定的格式输出&#xff1b; &#xff08;2&#xff09;解析模型输出&#xff0c;提取所需的信息 1、逗号分隔列表 CommaSeparatedListOutputParser&#xff1a;…...

数据库安全管理中的权限控制:保护数据资产的关键措施

title: 数据库安全管理中的权限控制:保护数据资产的关键措施 date: 2025/2/2 updated: 2025/2/2 author: cmdragon excerpt: 在信息化迅速发展的今天,数据库作为关键的数据存储和管理中心,已经成为了企业营运和决策的核心所在。然而,伴随着数据规模的不断扩大和数据价值…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...