喷水装置（一）几何里面最小覆盖问题
思路分析：
喷水装置的覆盖范围是个圆形，草坪是长方形，所以喷水装置的有效覆盖范围只能是紫色方框，这个方框的高是2米，公式：半径*半径=1*1+（宽/2）*(宽/2)，宽=2*sqrt(半径*半径-1）
图解：
程序代码：
#includeiostream#includealgorithm#includecmathusingnamespacestd;doublea[],r,len,s;boolcmp(doublea,doubleb){returnab;//大的喷水覆盖面积大}intmain(){intn,m;cinm;while(m--){cinn;for(inti=0;in;i++){cina;}sort(a,a+n,cmp);intcount=0;s=0;while(s20){//总长度是20r=a[count++];len=2*sqrt(r*r-1);s+=len;}coutcountendl;}return0;}
喷水装置（二）几何里面区间覆盖问题
思路分析：每个喷水器的喷水半径不一样，每个喷水器的坐标不一样，直接使用贪心不合适，可以采用喷水器与草坪边缘的两个交点进行排序。假设每个喷水器都会和草坪的一条边相交于left和right，left从小到大排序，如果left大小相同，那么再继续按照right由大到小排。
图解：
图解分析：
将所有区域按照左端点从小到大排序，依次处理每个区间，每次选择下一个区间的时候，要求选择能够覆盖当前区间的右端，并且保证下一个区间的右端是最大的，更新坐标，查找下一个。
程序代码：
#includeiostream#includecmath#includealgorithmusingnamespacestd;structp{doubleleft;doubleright;};boolcmp(px,py){returnx.lefty.left;//左交点从小到大排序}doublel,h;pa[];intmain(){intm,n;cinm;while(m--){cinnlh;for(inti=0;in;i++){doublex,r,f;cinxr;//求左右交点if(rh/2){f=sqrt(r*r-(h/2)*(h/2));}else{f=0;}a.left=x-f;a.right=x+f;}sort(a,a+n,cmp);doublestart=0,temp=0;intsum=0;for(inti=0;in;i++){//判断left左交点是否大于0，若最小的left都大于0，那么肯定不可能把草坪全部喷湿。if(a.left=start){temp=a.right;//暂时存储右坐标while(a.left=start){//（第一次从0开始）下一个的左交点一定小于上个装置的右交点（在满足这个条件的基础上，找覆盖面最大的）temp=max(temp,a.right);i++;if(i==n){break;}}start=temp;i--;//跳出循环的时候多加了一次，减回来sum++;}//如果最后边交点已经大于长度if(start=l){break;}}if(start=l){coutsumendl;}else{cout0endl;}}return0;}
会场安排
程序代码：
#includeiostream#includealgorithmusingnamespacestd;structac{intbegin;intend;}a[];boolcmp(aca,acb){returna.endb.end;}intmain(){intm,n,sum,t;cinm;while(m--){cinn;for(inti=0;in;i++){cina.begina.end;}sort(a,a+n,cmp);intcount=1;intj=0;for(inti=1;in;i++){if(a.begina[j].end){//保证下一个活动的开始大于上一个的结束count++;j=i;}}coutcountendl;}return0;}
一本通：金银岛
思路分析：金属可以被任意分割，需要单价贪心
程序代码：
#includeiostream#includecstdio#includealgorithmusingnamespacestd;constintN=;structG{intw;//重量intc;//价值doubleg;//单价}a[N];boolcmp(Ga,Gb){returna.gb.g;}intmain(){intk;intW,s;cink;while(k--){doublecount=0;cinWs;for(inti=0;is;i++){cina.wa.c;a.g=(double)a.c/a.w;}sort(a,a+s,cmp);for(inti=0;is;i++){if(W=a.w){count=count+a.c;W=W-a.w;}else{count=count+a.g*W;//装不下把剩余的装满就行了break;}}printf("%.2f\n",count);}return0;}预览时标签不可点收录于话题#个上一篇下一篇