洛谷【贪心算法】P1803 学习笔记

embedded/2024/12/22 0:14:05/

2024-12-20 - 第 41 篇
洛谷算法>贪心算法题单 - 算法>贪心算法 - 学习笔记
作者(Author): 郑龙浩 / 仟濹(CSND账号名)

P1803 凌乱的yyy / 线段覆盖

题目背景

快 noip 了,yyy 很紧张!

题目描述

现在各大 oj 上有 n n n 个比赛,每个比赛的开始、结束的时间点是知道的。

yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。

所以,他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加 2 2 2 个及以上的比赛。

输入格式

第一行是一个整数 n n n,接下来 n n n 行每行是 2 2 2 个整数 a i , b i ( a i < b i ) a_{i},b_{i}\ (a_{i}<b_{i}) ai,bi (ai<bi),表示比赛开始、结束的时间。

输出格式

一个整数最多参加的比赛数目。

样例 #1

样例输入 #1

3
0 2
2 4
1 3

样例输出 #1

2

提示

  • 对于 20 % 20\% 20% 的数据, n ≤ 10 n \le 10 n10
  • 对于 50 % 50\% 50% 的数据, n ≤ 1 0 3 n \le 10^3 n103
  • 对于 70 % 70\% 70% 的数据, n ≤ 1 0 5 n \le 10^{5} n105
  • 对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 0 6 1\le n \le 10^{6} 1n106 0 ≤ a i < b i ≤ 1 0 6 0 \le a_{i} < b_{i} \le 10^6 0ai<bi106

思路:

  1. 当然数据使用“结构体”存储,内容为:考试 开始时间、结束时间
  2. 只需要先将每一场比赛以【结束时间】排一次序,得到一个顺序为【升序】的结构体数组
  3. 循环之前,先定义一个 “变量记录” 【上一场】的【约束时间】
    进入循环,判断【下一场】的【开始时间】是否大于等于【上一场】的【约束时间】,
    • 如果大于等于,说明可以参加比赛,【约束时间】更新为【下一场】的【结束时间】,然后 参赛次数++,继续循环
    • 如果小于,说明不可以参加比赛,则直接进入循环~
  4. 直接参加比赛,然后计数,最后输出总次数就可以了。

代码:

// 洛谷P1803 凌乱的yyy / 线段覆盖 
// 看了题解才会做的
// 思路:
// 1. 当然数据使用“结构体”存储,内容为:考试 开始时间、结束时间
// 2. 只需要先将每一场比赛以【结束时间】排一次序,得到一个顺序为【升序】的结构体数组
// 3. 循环之前,先定义一个 “变量记录” 【上一场】的【约束时间】
//     进入循环,判断【下一场】的【开始时间】是否大于等于【上一场】的【约束时间】,
//     * 如果大于等于,说明可以参加比赛,【约束时间】更新为【下一场】的【结束时间】,然后 参赛次数++,继续循环
//     * 如果小于,说明不可以参加比赛,则直接进入循环~
// 4. 直接参加比赛,然后计数,最后输出总次数就可以了。
#include <iostream>
#include <algorithm>
using namespace std;
struct ddd{int start;int end;
};
bool cmp( ddd a, ddd b ){return a.end < b.end;
}
int main( void ){int n; // 比赛数量cin >> n;ddd data[ n ];for ( int i = 0; i < n; i ++ ){cin >> data[ i ].start >> data[ i ].end;}// 按照【结束时间】进行排序sort( data, data + n, cmp ); int count = 1; // 记录比赛数量 - 默认比赛一次,因为循环的时候是从第二场开始的,所以默认第一场比赛已经参加了// 而且 比赛数量本来就是 1 ~ 10^6,所以至少要参加 1 次比赛int last = data[ 0 ].end; // 记录上一场比赛的约束时间int i = 1; // 用来定位 下一场 比赛的 【开始时间】while( i < n ){if ( data[ i ].start >= last ){ // 如果 下一场比赛的【开始时间】大于等于上一场比赛的【约束时间】// 即【下一场】的【开始时间】 在 【上一场】的 【结束时间】 【后边】 --> 则可以参加比赛count ++; // 可以参加比赛 -> 比赛数量 ++last = data[ i ].end; // 【上一场】的【约束时间】更新为 【下一场】的【结束时间】}i ++;}cout << count;return 0;
}

http://www.ppmy.cn/embedded/147657.html

相关文章

<mutex>注释 11:重新思考与猜测、补充锁的睡眠与唤醒机制,结合 linux0.11 操作系统代码的辅助(上)

&#xff08;46&#xff09;问题的起源&#xff1a; 因为上面的内核代码&#xff0c;我们编写多线程代码时&#xff0c;对手里的家伙事不那么自信。但我们知道&#xff0c;多线程在竞争锁时&#xff0c;若得不到锁&#xff0c;会进入睡眠&#xff0c;并会在被唤醒后重新尝试得…

金碟中间件-AAS-V10.0安装

金蝶中间件AAS-V10.0 AAS-V10.0安装 1.解压AAS-v10.0安装包 unzip AAS-V10.zip2.更新license.xml cd /root/ApusicAS/aas# 这里要将license复制到该路径 [rootvdb1 aas]# ls bin docs jmods lib modules templates config domains …

前端解析超图的iserver xml

前端解析超图的iserver xml const res await axios.get(url)const xmlDom new DOMParser().parseFromString(res.data, text/xml);// 获取versionconst version xmlDom.getElementsByTagNameNS(*, ServiceTypeVersion)[0].textContent// 获取layerconst layerDom xmlDom.ge…

发布/部署WebApi服务器(IIS+.NET8+ASP.NETCore)

CS软件授权注册系统-发布/部署WebApi服务器(IIS.NET8ASP.NETCore) 目录 本文摘要VS2022配置发布VS2022发布WebApiIIS服务器部署WebApi 将程序文件复制到云服务器添加网站配置应用程序池配置dns域名配置端口阿里云ECS服务器配置19980端口配置https协议 (申请ssl证书)测试WebAp…

遥感影像目标检测:从CNN(Faster-RCNN)到Transformer(DETR

我国高分辨率对地观测系统重大专项已全面启动&#xff0c;高空间、高光谱、高时间分辨率和宽地面覆盖于一体的全球天空地一体化立体对地观测网逐步形成&#xff0c;将成为保障国家安全的基础性和战略性资源。未来10年全球每天获取的观测数据将超过10PB&#xff0c;遥感大数据时…

metagpt中ActionNode的用法

目录 整体流程1. 基础组件&#xff1a;2. SIMPLE_THINK_NODE 和 SIMPLE_CHECK_NODE&#xff1a;3. THINK_NODES 类&#xff1a;4. ThinkAction 类&#xff1a;5. SimplePrint 类&#xff1a;6. Printer 类&#xff1a;7. main 函数&#xff1a;总结&#xff1a;主要执行流程&am…

腾讯云全方位安全防护!

在流量暴增的数字时代&#xff0c;电商大促、在线直播、金融交易等场景下&#xff0c;业务暴涨固然可喜&#xff0c;但随之而来的系统压力和网络攻击也让人寝食难安。系统崩溃、访问卡顿、数据泄露……这些问题不仅影响用户体验&#xff0c;更可能让你失去市场和客户的信任。 …

面试题整理11----简述Pod创建过程

面试题整理11----简述Pod创建过程 1. 提交Pod定义2. API Server处理请求3. 调度器选择节点4. 绑定Pod至Node5. Kubelet执行6. Pod就绪和运行 在Kubernetes中&#xff0c;Pod的创建过程涉及多个组件的协同工作&#xff0c;确保Pod能够高效、稳定地运行。以下是Pod创建过程的详细…