贪心习题.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,NYOJ-6 喷水,装置,现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0Ri15)的圆被湿润，这有充足的喷水装置i（1i600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。,解题思路,这个题目思路很容易想，肯定是优先使用半径大的喷水装置。因为半径越大的喷水装置所能覆盖的范围就越大。,其实这个确定优先选择哪一个的过程就是贪心选择的过程。,所以本题就是先对所有的喷水装置半径排序，计算出，每个喷水装置所能覆盖的长度。每次都选出当前半径最大的，直到能覆盖完所有的草地。,NYOJ-47 过河问题,在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。,思考：,一、如果有四个人，过河的方案有哪几种，该如根据什么来选取方案。,（a+c与2*b的关系）,二、如果有五个人，过河方案应如何选取。,HDOJ:1009FatMouse Trade,2026/1/14 周三,5,Problem Description,FatMouse prepared M pounds of cat food,ready to trade with the cats guarding the warehouse containing his favorite food,JavaBean.The warehouse has N rooms.The i-th room contains Ji pounds of JavaBeans and requires Fi pounds of cat food.FatMouse does not have to trade for all the JavaBeans in the room,instead,he may get Ji*a%pounds of JavaBeans if he pays Fi*a%pounds of cat food.Here a is a real number.Now he is assigning this homework to you:tell him the maximum amount of JavaBeans he can obtain.,2026/1/14 周三,6,Input,：,The input consists of multiple test cases.Each test case begins with a line containing two non-negative integers M and N.Then N lines follow,each contains two non-negative integers Ji and Fi respectively.The last test case is followed by two-1s.All integers are not greater than 1000.,Output,：,For each test case,print in a single line a real number accurate up to 3 decimal places,which is the maximum amount of JavaBeans that FatMouse can obtain.,2026/1/14 周三,7,Sample Input,5 3,（,5,个，有,3,个交换的地方）,7 2,（,2,换,7,）,4 3,5 2,20 3,25 18,24 15,15 10,-1-1,Sample Output,13.333,31.500,贪心准则：,很明显，每次总是先挑最划算的交易，一直把手里的,cat food,都换完,2026/1/14 周三,8,算法基本思想：,输入（其中，交易数据,J,F,对放入数组）,对数组排序（按效益，降序）,按效益高低进行有序交易，一直把手里的,cat food,都换完。,输出得到的,Java Beans.,2026/1/14 周三,9,部分参考代码：,struct warehouse int bean,food;double r;,warehouse a1001;,2026/1/14 周三,10,.,sort(a,a+n,cmp);,catfood=m;javabean=0;for(i=0;in;i+)if(ai.foodb.r;,hdOJ1051,：,wooden stick,There is a pile of n wooden sticks.The length and weight of each stick are known in advance.The sticks are to be processed by a woodworking machine in one by one fashion.It needs some time,called setup time,for the machine to prepare processing a stick.The setup times are associated with cleaning operations and changing tools and shapes in the machine.The setup times of the woodworking machine are given as follows:,(a)The setup time for the first wooden stick is 1 minute.(b)Right after processing a stick of length l and weight w,the machine will need no setup time for a stick of length l and weight w if l=l and w,大王最弱 田忌最弱,PK,大王最弱,如果 田忌最弱,大王最强 田忌最强,PK,大王最强,（先考虑最强的马发挥最大的作用）,如果田忌最强,大王最强 田忌最弱,PK,大王最强,（反正一样是输，避免牺牲最强的马）,如果田忌最强,=,大王最强 田忌最弱,PK,大王最强,（在保证同等输赢的情况下，留住强的马）,2026/1/14 周三,23,这样的贪心策略能否保证最优解？,注意到没有,贪心往往要结合一定的排序策略,老鼠交易,换算的比率大小,事件序列,事件结束的时间,木板,木板的长,&,宽,赛马,马的速度,2026/1/14 周三,24,1340,：矩形移动,周三,25,输入：,第一行为一个整数,n(n=10000),，表示长方形的个数；接下来有,n,行，每行有三个整数,x1,y1,x2(0=x1x2200000,0=y1231),，分别表示一个长方形左下端点的横坐标和纵坐标，以及右下端点的横坐标。,输出：,输出最小矩形的面积。,样本输入,3,1 23 3,3 40 7,3 17 6,2026/1/14 周三,26,样本输出：,12,分析：,水平方向不能移动，意味着,矩形的宽度能否确定？,（,x,坐标的最小值,?,最大值？）,y,坐标的值有没有关系？,怎样让长方形得到有效的邻接，从而减少纵向的长度？,2026/1/14 周三,27,继续分析：,问题转换为：需要多少行，各个长方形才不会重叠？,资源调度问题？,什么是资源？水平的一行，在同一行中是不能重叠的。,2026/1/14 周三,28,比较：,事件序列：,用一个资源满足尽可能多的需求,现在的问题：,用尽可能少的资源（不同行）安排所有的需求（在一行中占据不重叠的位置）,类似问题：,教室排课,2026/1/14 周三,29,贪心策略：,优先选择先出现的长方形进行排列,.,如果能排在已有的行，则排在已有的行,否则，新增加一行；,2026/1/14 周三,30,具体做法：,按先后次序，让所有的长方形排成行,.,首先选第一个出现的长方形，排在第一行；,接着继续选长方形，,只要能接在已有行的后面，就不需要增加行,。,要多出一行的判断依据？,前面每一行的最后矩形，都和现在判断的矩形叠加,.,2026/1/14 周三,31,细节处理策略,X,坐标的处理：,struct xx int value,flag;,flag:0,代表左坐标，,flag:1,代表右坐标,所有的坐标根据,value,排序；,取第一个,x,坐标，,line=1,，,nl=1;,接下去依次取,x,坐标,如果,flag,为,1 nr+=1,如果,flag,为,0,nl+=1,如果,line+nrp2.x;,sort(points,points+10,Cmp);,大家看明白，传参时传递的函数该如何写没有？也就是说，只需要指明，p1,p2这两个点，如果p1在前面就返回true，如果p2在前面就返回false，然后，sort之后，它就按你的要求进行了排序。,