菜单

贪心法小关卡-洛谷试炼场 贪心法(二)

十月 29, 2018 - 教程系列, 算法

前言

上一次写了4道比较简单的问题,说实话不太需要什么思考含量,也就是洛谷试炼场贪心法的前4道题,这次给出的3道题解是针对之后的三道ww

第一题 P1094-纪念品分组

题目描述

元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品, 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。

Input

共$n+2$行:
第1行包括一个整数$w$,为每组纪念品价格之和的上限。
第2行为一个整数$n$,表示购来的纪念品的总件数$G$。
第3至$n+2$行每行包含一个正整数$P_{i}(5\leq P_{i} \leq w)$表示所对应的纪念品的价格。

Output

一个整数,即最少的分组数目。

Sample Input

100
9
90
20
20
30
50
60
70
80
90

Sample Output

6

题目分析

说来惭愧,这个题我wa了十几次,在我wa了第十三发之后我重新看题的时候发现每组只能包括两件纪念品,差点气的我砸电脑嘤嘤嘤(后来考虑到新的surface就没下手23333)。
回头看题,要求分组数量尽可能的少,而且最多两个一组,所以题目变得比较清晰明了了,排序之后,前面取一个,后面取一个,如果加和超过总数,就只取后面的大的单独作为一组,再利用小的和下一个最大的匹配就好。代码量不大。

代码实现

第二题 P1803-凌乱的yyy / 线段覆盖

题目描述

现在各大oj上有n个比赛,每个比赛的开始、结束的时间点是知道的。
yyy认为,参加越多的比赛,noip就能考的越好(假的)
所以,他想知道他最多能参加几个比赛。
由于yyy是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加2个及以上的比赛。

Input

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

Output

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

Sample Input

3
0 2
2 4
1 3

Sample Output

2

题目分析

超级经典的一道贪心法的题目改编,同一道题有各种版本,什么线段覆盖,什么最多工作,还有这个最多参加一个比赛,其实都可以等效成一个问题。
就这道题来说,只要我们每次选取能够选取的最早结束的比赛,就能选出能够最多的次数,这里引用一段《挑战程序设计竞赛》的话:

与其他选择方案相比,该算法的选择方案在选取了相同数量的更早开始的工作时,其最终结束时间不会比其他方案的更晚。

这句话其实说的非常到位,我们优先选择结束时间早的方案,就可以保证我们在选择同样数量的比赛后保证时间一定比其他的少。也就是这道题的核心思想。

代码实现

第三题 P1031-均分纸牌

题目描述

有N堆纸牌,编号分别为1,2,…,N。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动.
移牌规则为:在编号为1堆上取的纸牌,只能移到编号为2的堆上;在编号为N的堆上取的纸牌,只能移到编号为N−1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。
例如N=4,4堆纸牌数分别为:
①9②8③17④6
移动3次可达到目的:
从 ③ 取4张牌放到 ④ (9,8,13,10)-> 从 ③ 取3张牌放到 ②(9,11,10,10)-> 从 ② 取11张牌放到①(10,10,10,10)。

Input

两行
第一行为:$N$ $(1 \leq N \leq 100)$ N堆纸牌
第二行为:$A_{1}$, $A_{2}$,…,$A_{n}$$(1 \leq A_{i} \leq 100000)$每堆纸牌初始数

Output

一行:即所有堆均达到相等时的最少移动次数。

Sample Input

4
9 8 17 6

Sample Output

3

题目分析

这道题乍一看没什么思路,因为如果按照题意直接考虑,要从最多的一推开始同时向左向右开始分摊,这样的复杂度想一想就超了不知道多少了QAQ
这道题的正确思路是:
首先求出平均数,再从数组第一个开始向后遍历,先看和平均数相差多少,从它的下一位像借位一样的借过来把自己凑成平均数,移动次数的技术加一;如果本身就是平均数就直接跳到下一个。
为什么这样是正确的呢?
我们首先需要明确一点,只能从一摞向直接相邻的两堆移动,所以这样相当于把最开始的模拟的过程逆了过来,因为不管是当前堆比平均值多出多少还是差多少,都是要向自己旁边的堆分摊或者索要。至于为什么最小,首先,从头开始遍历也能保证一次遍历之后所有的值都变成平均数;其次,因为前一堆已经处理成平均数了,所以不需要再利用额外的操作去修改值;最后,即使出现负值,也只要按照借位的思想来思考,就会发现并不会影响最后的结果,本质上是改变了移动的顺序,让一位上暂时出现负数,并不会影响总的移动次数。
明确了以上几点,整个过程就变得异常简单了,代码也不长。

代码实现

后记

这几道题比起之前的三道题有了一些思维含量,尤其是最后一道题的思考方式有些不合常规,说实话不是很好想。
至此,洛谷试炼场贪心法的题解就告一段落了,这两篇文章就算是自己时隔两个多月回坑写博客的练手吧,最近关于自己的事情也想了很多,对于自己的博客的内容,也决定要扩充一些了,无论是读的书还是最近的想法什么的,都想尝试着记录下来,算是为自己上了大学之后就几乎废弃的随笔的习惯换一种方式恢复起来吧。
不过不一定坚持的下去就是了2333333.

标签:, ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注