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

devtools/2024/12/23 13:24:51/

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/devtools/144109.html

相关文章

单元测试总结

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 Hello&#xff01;大家好&#xff0c;我是一个专注于分享软件测试干货的测试开发。 对于软件测试&#xff0c;我们先按照开发阶段来进行划分&#xff0c;将软件测…

在C#中,可以通过使用委托(delegate)或者是事件(event)来将方法作为参数传递。

using System; public class Program { // 定义一个委托类型&#xff0c;它表示一个接受一个int参数并返回int的方法 public delegate int ProcessIntDelegate(int value); // 使用委托的方法 public static int ProcessNumber(int number, ProcessIntDele…

如何在Anaconda的虚拟环境中下载Python包

一、首先查看conda下的虚拟环境 使用conda info -e查看当前conda下的虚拟环境&#xff1a; conda info -e 二、激活要添加Python包的虚拟环境 其中base是基础环境&#xff0c;这里我们选择conda_env这个虚拟环境 conda activate conda_env 三、使用conda命令安装需要的Pyth…

C# opencvsharp 流程化-脚本化-(2)ROI

ROI ROI也是经常需要使用的方法。特别是在图像编辑中。ROI又称感兴趣的区域&#xff0c;但是图像是矩阵是矩形的&#xff0c;感兴趣的是乱八七糟的&#xff0c;所以还有一个Mask需要了解一下的。 public class RoiStep : IImageProcessingStep{public ImageProcessingStepType…

二十一、Ingress 进阶实践

架构参考 使用hostnetwork,推荐的方式,使用单独的物理服务器,不部署业务pod的主机。 一、Ingress Nginx Controller 安装 采用helm的安装方式,进行部署。 官网地址: https://kubernetes.github.io/ingress-nginx/deploy/ github地址: https://github.com/kubernetes/in…

springcloud-gateway获取应用响应信息乱码

客户端通过springcloud gateway跳转访问tongweb上的应用&#xff0c;接口响应信息乱码。使用postman直接访问tongweb上的应用&#xff0c;响应信息显示正常。 用户gateway中自定义了实现GlobalFilter的Filter类&#xff0c;在该类中获取了上游应用接口的响应信息&#xff0c;直…

WPF 布局控件

wpf 布局控件有很多&#xff0c;常用的有&#xff1a;Grid, UniformGrid, Border, StackPanel, WrapPanel, DockPanel。 1. Grid Grid 经常作为控件的 Content 使用&#xff0c;常作为 Windows, UserControl 等 UI 元素的根节点。它用来展示一个 n 行 n 列的排版。 因此就有…

前端如何实现大文件上传

‌在前端实现大文件上传的主要方法包括分片上传、断点续传、WebSocket上传和通过第三方服务上传。‌ ‌分片上传‌&#xff1a;将大文件切割成多个小片段&#xff0c;然后分别上传。可以使用HTML5的File API和Blob对象&#xff0c;通过FileReader读取文件内容&#xff0c;然后使…