貪心策略是將左端點從小到大排序，選擇右端點，使得右端點盡量覆蓋的最遠

AC:

#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; const int MAX=10001; struct interval{double left,right; }; bool cmp(interval a,interval b){return a.left<b.left; } int main() {int i,j,pump_num,len,wight,times,count,flag;double wight_2;interval a[MAX];scanf("%d",×);while(times--){flag = 1;count = 0;scanf("%d%d%d",&pump_num,&len,&wight);wight_2=wight/2.000000;for(i=0;i<pump_num;i++){int temp_x,temp_radous;double temp_w;scanf("%d%d",&temp_x,&temp_radous);temp_w=sqrt(temp_radous*temp_radous-wight_2*wight_2);if(temp_w>0){a[i].left=temp_x-temp_w; //轉換成區間問題a[i].right=temp_x+temp_w;}}sort(a,a+pump_num,cmp);double Max=0; //比上一個裝置及之前的裝置（不是光上一個裝置覆蓋的長度）多覆蓋的長度,一定要記住，Max是這次會闊展（只是比上一次多的長度，而不一定會是某一個區間的長度（一般不會是區間長度））的長度double sum=0; //在使用本裝置之前已經被覆蓋的長度while(sum<len){Max=0;for(i=0;i<pump_num&&a[i].left<=sum;i++) //a[i].left<=sum是為了避免最后一幅圖中紫色部分中假設沒有第二條線的情況{if(a[i].right-sum>Max) //選出最后一幅圖中的線段三，因為線段三可以在相接前面（不能斷開）的線段的基礎上覆蓋的更遠{Max=a[i].right-sum;}}if(Max==0) //while下面初始化Max為0，就是說沒有找到一個裝置可以接著向后面覆蓋，也就是說后面的沒辦法覆蓋了{flag = 0;break;}else{count++;sum+=Max; //現在已經覆蓋到了上一次覆蓋到的地方加上本次又向后擴展的長度 }}if(flag)printf("%d\n",count);elseprintf("0\n");}return 0; }

總結

以上是生活随笔為你收集整理的nyoj 12（区间覆盖）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。