贪心算法练习题

《贪心算法练习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、贪心算法1.喷水装置（一）描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0

2、5根据日常生活知道，选择半径越大的装置，所用的数目越少。因此，可以先对半径排序，然后选择半径大的。另外，当装置刚好喷到矩形的顶点时，数目最少。此时只要装置的有效喷水距离的和不小于20时，输出此时的装置数目即可。2.喷水装置（二）时间限制：3000 ms 

3、 内存限制：65535 KB难度：4描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。输入第一行输入一个正整数N表示共有

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

5、学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。输入第一行是一个整型数m(m<100)表示共有m组测试数据。每组测试数据的第一行是一个整数n(1

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

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

8、eOutput0355.过河问题时间限制：1000 ms 

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

10、示共有N个人要过河每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。