- BC20270003's blog
题解:P1 「一本通 1.1 例 1」活动安排
- 8 months ago @
这是一道很经典的贪心题
做法主要分几个步骤:
一、按照每个活动的结束时间升序。
二、每次先选在可以安排的活动中结束时间最小的,然后计算总个数。
三、输出答案。
证明:
首先,在选第一个活动的时候,如果是要选某一个活动的时候,那么那个活动肯定是挤掉的活动最少的那个,毕竟如果都被挤掉了,那还选什么?
然后,在选后面的活动的时候也是同理。
那么怎么选挤掉的活动最少的那个?
答案是选结束时间最早的那个!
然后,我们就可以轻松的解出这道题了ψ(`∇´)ψ