贪心算法练习题

1、贪心算法1.喷水装置（一）描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。输入第一行m表示有m组测试数据每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。输出输出所用装置的个数样例输入252 3.2 4 4.5 6 101 2 3 1 2 1.2 3 1.1 1

2、2样例输出25根据日常生活知道，选择半径越大的装置，所用的数目越少。因此，可以先对半径排序，然后选择半径大的。另外，当装置刚好喷到矩形的顶点时，数目最少。此时只要装置的有效喷水距离的和不小于20时，输出此时的装置数目即可。2.喷水装置（二）时间限制：3000 ms  |  内存限制：65535 KB难度：4描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。输入第一行输

3、入一个正整数N表示共有n次测试数据。每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。输出每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。如果不存在一种能够把整个草坪湿润的方案，请输出0。样例输入22 8 61 14 52 10 64 56 5样例输出123.会场安排问题描述学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学

4、校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。输入第一行是一个整型数m(m<100)表示共有m组测试数据。每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)输出对于每一组输入，输出最多能够安排的活动数量。每组的输出占一行样例输入221 1010 1131 1010 1111 20样例输出12提示注意：如果上一个活动在T时间结束，下一个

5、活动最早应该在T+1时间开始。解题思路：这是一个贪心法中选择不相交区间的问题。先对活动结束时间从小到大排序，排序的同时活动的起始时间也要跟着变化。而且，结束时间最小的活动一定会安排，不然这段时间就白白浪费了。后一个活动的起始时间如果比前一个活动的结束时间大，即两个活动没有相交时间，就把这个活动也安排上。就这样一直找到结束时间最大的，输出时间数目即可。排序时可用下面的方法，排序的同时起始时间也跟着变了。如果输入0 63 41 92 8则排序后的结果就是3 40 62 81 9Sample Output0354.Doing homework问题描述：Ignatius比赛回来之后，每位老师给Igna

6、tius一个交作业的最后期限，如果交不上去就扣分。每门作业都要一天时间完成，求最少扣多少分。先输入一个T表示有T组测试数据，接下来每组数据先输入一个N，代表有N个作业，然后输入两行，第一行表示每门作业要交的日期，第二行表示对应的如果不交这门作业要扣的分数。输出要扣的最少分数。解题思路：先对日期从小到大排序，如果日期相同，则扣分多的排在前面。如果相同日期内有扣分多的，则就用前面做扣分少的作业的时间来做这门作业；如果没有比他小的，就扣这门作业的分。Sample Input333 3 310 5 131 3 16 2 371 4 6 4 2 4 33 2 1 7 6 5 4 Sample

7、Output0355.过河问题时间限制：1000 ms  |  内存限制：65535 KB难度：5描述在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。 输入第一行是一个整数T(1<=T<=20)表示测试数据的组数每组测试数据的第一行是一个整数N(

8、1<=N<=1000)表示共有N个人要过河每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0<Si<=100)输出输出所有人都过河需要用的最少时间样例输入141 2 5 10样例输出17分析：如果n=1或者n=2，所有人直接过河即可；如果n=3，用时最短的和用时最长的一起过去，然后用时最短的回来，再和剩下的一个人过去 ；如果n>=4，设a0表示用时最短的人所用的时间，a1为用时第二短的人所用的时间，an-1表示用时最长的人所用的时间，an-2表示用时第二长的人所用的时间。那么：当2a1 + a0 + an-1 > 2a0 + an-1 + a

9、n-2时，就先让用时最短的人和用时最长的人一起过去，然后用时最短的回来，接着让用时最短的和用时第二长的一起过去，再让用时最短的回来。否则，就先让用时最短的和用时第二短的一起过去，然后用时最短的回来，接着让用时最长和用时第二长的一起过去，再让用时第二短的回来。这样就相当于剩下了n-2个人。对这n-2个人执行相同的操作，知道剩下不足4个人即可。6.摘枇杷时间限制：2000 ms  |  内存限制：65535 KB难度：3描述理工学院的枇杷快熟了，ok，大家都懂得。而且大家都知道，学校的枇杷树都是一列一列的。现在小Y同学已经在筹划怎么摘枇杷了。现在我们假设有一

10、列枇杷树，而且每棵枇杷树上枇杷果的数量小Y都已经知道了。假设现在有n棵枇杷树，小Y可以把这n棵枇杷树分成m组，每组枇杷果的数量是这组内每棵枇杷树上枇杷果数量的和。注意，每组的枇杷树必须是连续的。（每组最少1棵树，最多n棵树）。小Y把枇杷往寝室拿的时候是一组一组拿的，所花费的力气等于这m组中枇杷果最多的那组枇杷果的数量。现在小Y想花尽量少的力气把这些枇杷果拿回寝室。输入多组测试数据，以EOF结束（<= 100组）每组测试数据第一行有两个数n（n <= 1000）和m（1 <=m <= n）第二行有n个数，分别代表每颗树上枇杷果的数量输出输出小Y同学所花费的最小的力气，每个

11、结果占一行。样例输入3 21 2 37 51 4 3 1 5 2 4样例输出357.疯牛时间限制：1000 ms  |  内存限制：65535 KB难度：4描述农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,.,xN (0 <= xi <= 1,000,000,000).但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？输入有多组测试数据，以EOF结束。第一行：空格分隔的两个整数N和C第二行第N+1行：分别指出了xi的位置输出每组测试数据输出一个整数，满足题意的最大的最小值，注意换行。样例输入5 312849样例输出3题意要表达的是：把C头牛放到N个带有编号的隔间里，使得任意两头牛所在的隔间编号的最小差值最大。例如样例排完序后变成1 2 4 8 9，那么1位置放一头牛，4位置放一头牛，它们的差值为3；最后一头牛放在8或9位置都可以，和4位置的差值分别为4、5，和1位置的差值