【贪心算法】CF Emergency Evacuation
2024-10-09 20:24:19
题目大意
给你一个车厢和一些人,这些人都坐在座位上,求这些人全部出去的时间最小值。
样例1输入
5 2 7
1 1
1 2
1 3
2 3
2 4
4 4
5 2
样例1输出
9
样例2输入
500 500 16
1 1
1 2
1 999
1 1000
2 1
2 2
2 999
2 1000
3 1
3 2
3 999
3 1000
499 500
499 501
499 999
499 1000
样例2输出
1008
思路
逆向思维,利用贪心。
假设所有人都还没有上车,所以需要把人们从车门处送回原来的位置。
可以把2每个人从车门到原来座位之间距离降序排序,
这样就可以让座位离车门较远的人先上车,车门离座位较近的人后上车,
这样得出的答案就可以使花费的时间达到最小,就是我们需要的最优答案。
最新文章
- 自定义置顶TOP按钮
- Hi,我还没死(屎)
- Unity学习疑问记录之新GUI
- python数据结构与算法——图的最短路径(Dijkstra算法)
- 10301 MySQL各个版本区别及下载
- Linux 随笔1
- 安装FreeMind
- poj 1348 Computing (四个数的加减乘除四则运算)
- 关系型数据库遵循ACID规则
- MySQL show binglog event in 'log_name'
- ●SPOJ 8222 NSUBSTR–Substrings(后缀自动机)
- Nginx+Keepalived 集群方案
- asp.net获取当前请求的url
- docker zabbix
- 配置opensips经验总结
- *jQuery选择器总结(原创:最全、最系统、实例展示)
- 【java】ThreadLocal线程变量的实现原理和使用场景
- Buffer和cahce的区别
- Linq in GroupBy GroupJoin
- vue router的浏览器跳转行为