更新时间:2022-09-20 09:30:35
2 2 8 6 1 1 4 5 2 10 6 4 5 6 5
1 2
C代码如下
1 #include "stdio.h" 2 #include "math.h" 3 typedef struct _Equip//区间的结构体 4 { 5 float L; 6 float R; 7 }Equip; 8 9 void Q_sort(Equip **a,int low,int heigh)//对区间按开始端进行升序排序 10 { 11 if(low < heigh) 12 { 13 int i = low,j = heigh; 14 Equip * temp; 15 temp = a[i]; 16 while(i < j) 17 { 18 while(i < j && a[j]->L > temp->L) 19 { 20 j --; 21 } 22 if(i < j) 23 { 24 a[i] = a[j]; 25 i++; 26 } 27 while(i < j && a[i]->L <= temp->L) 28 { 29 i ++; 30 } 31 if(i < j) 32 { 33 a[j] = a[i]; 34 j --; 35 } 36 } 37 a[i] = temp; 38 Q_sort(a,low,i - 1); 39 Q_sort(a,i+1,heigh); 40 } 41 } 42 Equip buf[10000]; 43 Equip *Si[10000]; 44 45 //寻找从begin开始到end-1之间符合条件的一个区间 46 //即开始端 <= Rc 的所有小区间中结束端最大的那个小区间 47 int findmaxR(int begin,int end) 48 { 49 int k = begain; 50 for(int i = begain;i < end;i++) 51 { 52 if(Si[i]->R >= Si[k]->R) 53 { 54 k = i; 55 } 56 } 57 return k; 58 } 59 int main() 60 { 61 int i,j,m,n,count,s; 62 float w,h,Rc,Lc,x,r; 63 while(scanf("%d",&m) != EOF) 64 { 65 for(i = 0;i < m;i++) 66 { 67 scanf("%d%f%f",&n,&w,&h); 68 s = 0; 69 for(j = 0;j < n;j++) 70 { 71 scanf("%f%f",&x,&r); 72 if(r > h/2.0) 73 { 74 buf[j].L =x - sqrt(r * r - h * h / 4.0); 75 if(buf[j].L < 0.0) 76 { 77 buf[j].L = 0.0; 78 } 79 buf[j].R =x + sqrt(r * r - h * h / 4.0); 80 if(buf[j].R > w) 81 { 82 buf[j].R = w; 83 } 84 Si[s++] = &buf[j]; 85 } 86 } 87 Q_sort(Si,0,s-1);//从这里到前边都是准备工作,后边开始贪心了 88 Rc = 0.0; 89 for(j = 0;j < s && Rc < w;) 90 { 91 if(Si[j]->L <= Rc) 92 { 93 int k; 94 for(k = j;k < s;k++) 95 { 96 if(Si[k]->L > Rc) 97 { 98 break; 99 } 100 } 101 int maxR = findmaxR(j,k); 102 count ++; 103 Rc = Si[maxR]->R; 104 j = maxR +1; 105 } 106 else 107 { 108 break; 109 } 110 } 111 if(Rc < w) 112 printf("0\n"); 113 else 114 printf("%d\n",count); 115 } 116 } 117 }
本文转自郝峰波博客园博客,原文链接:http://www.cnblogs.com/fengbohello/archive/2013/01/25/2876233.html,如需转载请自行联系原作者