洛谷 P1803题解 java 贪心
2021/10/22 22:12:43
本文主要是介绍洛谷 P1803题解 java 贪心,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
现在各大 oj 上有 nn 个比赛,每个比赛的开始、结束的时间点是知道的。
yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。
所以,他想知道他最多能参加几个比赛。
由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加 22 个及以上的比赛。
输入格式
第一行是一个正数n,接下来n行每行是2个整数ai,bi,表示比赛开始时间,结束时间。
输出格式
一个整数最多参加的比赛数目。
输入输出样例
输入
3
0 2
2 4
1 3
输出
2
做题思路
相当于就是在数轴上画区间,只要两个区间没有重叠的部分就ok。
如何判断两个区间没有重复,就是判断前一个区间的末尾有没有小于后一个区间的开始。这样比较关系出来后就需要进行排序,但是是按照开始时间排还是结束时间排,这是一个问题,因为我刚开始想的是按照开始时间排序,很不幸,全wa。
先来分析下为什么不能能按照开始时间排序,举个例子
1 10000
2 1000
3 100
4 10
如果按照开始时间进行排序,就是上边的顺序,但是从头开始遍历,判断前一个的结束是否大于等于后一个的开始,如果这样判断,就一场比赛也参加不了。但是如果按照结束时间开始排序,这样就是
4 10
3 100
2 1000
1 10000
将第一个的结束时间设置为最小的结束时间,从第二个开始判断,如果后面的开始时间大于等于前面的结束时间,就表示这个比赛可以参与,就把后面的结束时间设置为最小的结束时间。
上代码:
for(int i=1;i<n;i++) { if(list.get(i).begin>=minOver) { minOver=list.get(i).over; cnt++; } }
接下来就是完整的解题代码
import java.util.*; public class Main { static class Time { int begin; int over; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); ArrayList<Time> list=new ArrayList<>(); for(int i=0;i<n;i++) { Time time=new Time(); time.begin=sc.nextInt(); time.over=sc.nextInt(); list.add(time); } int cnt=1; list.sort((o1,o2)->o1.over-o2.over); int minOver=list.get(0).over; for(int i=1;i<n;i++) { if(list.get(i).begin>=minOver) { minOver=list.get(i).over; cnt++; } } System.out.println(cnt); } }
有些人可能疑惑这里sum的初始值为什么是1,因为就算看起来这些时间都有重合,最少都能参加一场比赛
总结
选择不相交区间问题
经典的贪心题
贪心的策略是先给所有的区间按照右边界排序
其中一定要选择第一个区间
这篇关于洛谷 P1803题解 java 贪心的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求