贪心算法习题.docx

喷水装置（一）时间限制：3000ms | 内存限制：65535KB难度：3描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0Ri15)的圆被湿润，这有充足的喷水装置i（1i600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。输入第一行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样例输出25喷水装置（二）时间限制：3000ms | 内存限制：65535KB难度：4描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。输入第一行输入一个正整数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样例输出12会场安排问题时间限制：3000ms | 内存限制：65535KB难度：4描述学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。输入第一行是一个整型数m(m100)表示共有m组测试数据。每组测试数据的第一行是一个整数n(1n10000)表示该测试数据共有n个活动。随后的n行，每行有两个正整数Bi,Ei(0=Bi,Ei10000),分别表示第i个活动的起始与结束时间（Bi=Ei)输出对于每一组输入，输出最多能够安排的活动数量。每组的输出占一行样例输入221 1010 1131 1010 1111 20样例输出12Gone Fishing时间限制：3000ms | 内存限制：65535KB难度：5描述John is going on a fishing trip. He has h hours available (1 = h = 16), and there are n lakes in the area (2 = n = 25) all reachable along a single, one-way road. John starts at lake 1, but he can finish at any lake he wants. He can only travel from one lake to the next one, but he does not have to stop at any lake unless he wishes to. For each i = 1,.,n - 1, the number of 5-minute intervals it takes to travel from lake i to lake i + 1 is denoted ti (0 ti = 0 ), is known. Each 5 minutes of fishing decreases the number of fish expected to be caught in the next 5-minute interval by a constant rate of di (di = 0). If the number of fish expected to be caught in an interval is less than or equal to di , there will be no more fish left in the lake in the next interval. To simplify the planning, John assumes that no one else will be fishing at the lakes to affect the number of fish he expects to catch.Write a program to help John plan his fishing trip to maximize the number of fish expected to be caught. The number of minutes spent at each lake must be a multiple of 5.输入You will be given a number of cases in the input. Each case starts with a line containing n. This is followed by a line containing h. Next, there is a line of n integers specifying fi (1 = i =n), then a line of n integers di (1 =i =n), and finally, a line of n - 1 integers ti (1 =i =n - 1). Input is terminated by a case in which n = 0.输出For each test case, print the number of minutes spent at each lake, separated by commas, for the plan achieving the maximum number of fish expected to be caught (you should print the entire plan on one line even if it exceeds 80 characters). This is followed by a line containing the number of fish expected.If multiple plans exist, choose the one that spends as long as possible at lake 1, even if no fish are expected to be caught in some intervals. If there is still a tie, choose the one that spends as long as possible at lake 2, and so on. Insert a blank line between cases.样例输入2 1 10 1 2 5 2 4 4 10 15 20 17 0 3 4 3 1 2 3 4 4 10 15 50 30 0 3 4 3 1 2 3 0 样例输出45, 5 Number of fish expected: 31 240, 0, 0, 0 Number of fish expected: 480 115, 10, 50, 35 Number of fish expected: 724 过河问题时间限制：1000ms | 内存限制：65535KB难度：5描述在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。输入第一行是一个整数T(1=T=20)表示测试数据的组数每组测试数据的第一行是一个整数N(1=N=1000)表示共有N个人要过河每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0Si=100)输出输出所有人都过河需要用的最少时间样例输入141 2 5 10样例输出17心急的C小加时间限制：1000ms | 内存限制：65535KB难度：4描述C小加有一些木棒，它们的长度和质量都已经知道，需要一个机器处理这些木棒，机器开启的时候需要耗费一个单位的时间，如果第i+1个木棒的重量和长度都大于等于第i个处理的木棒，那么将不会耗费时间，否则需要消耗一个单位的时间。因为急着去约会，C小加想在最短的时间内把木棒处理完，你能告诉他应该怎样做吗？输入第一行是一个整数T(1T1500)，表示输入数据一共有T组。每组测试数据的第一行是一个整数N（1=N=5000）,表示有N个木棒。接下来的一行分别输入N个木棒的L，W（0 L ,W = 10000），用一个空格隔开，分别表示木棒的长度和质量。输出处理这些木棒的最短时间。样例输入3 5 4 9 5 2 2 1 3 5 1 4 3 2 2 1 1 2 2 3 1 3 2 2 3 1 样例输出213BUYING FEED时间限制：3000ms | 内存限制：65535KB难度：4描述FarmerJohnneeds to travel to town to pick up K (1 = K = 100)pounds of feed. Driving D miles with K pounds of feed in his truck costsD*Kcents.The county feed lot has N (1 = N= 100) stores (conveniently numbered 1.N) that sell feed. Each store is located on a segment of the X axis whose length is E (1 = E = 350). Store i is atlocation X_i (0 X_i E) on the number line and can sellJohnas much as F_i (1 = F_i = 100) pounds of feed at a cost of C_i (1 = C_i = 1,000,000) cents per pound.Amazingly, a given point onthe X axis might have more than one store.FarmerJohnstartsat location 0 on this number line and can drive only in the positive direction, ultimately arriving at location E, with at leastKpounds of feed. He can stop at any of the feed stores along the way and buy any amount of feed up to the the stores limit.What is the minimum amount FarmerJohnhas to pay to buy and transport the K pounds of feed? FarmerJohnknows there is a solution.Consider a sample where FarmerJohnneeds two pounds of feed from three stores (locations: 1, 3, and 4) on a number line whose range is 0.5:012345-111Available pounds of feed122Cents per poundIt is best forJohnto buy one pound of feed from both the second and third stores. He must pay two cents to buy each pound of feed for a total cost of 4. WhenJohntravels from 3 to 4 he is moving 1 unit of length and he has 1 pound of feed so he must pay1*1 = 1 cents.WhenJohntravels from 4 to 5 heis moving one unit and he has 2 pounds of feed so he must pay 1*2 = 2 cents. The total cost is 4+1+2 = 7 cents.输入The first line of input contains a number c giving the number of cases that followThere are multi test cases ending with EOF.Each case starts with a line containing three space-separated integers: K, E, and NThen N lines follow :every line contains three space-separated integers: Xi Fi Ci输出For each case,Output A