UVa 10020 Minimal Converge

題意：
　　數線上有很多條線段，每條線段給左右兩端的座標(L,R)，題目問如何用最少的線段去覆蓋[0,M]這個範圍

想法：

1. 依照L值來排序
2. 第一次left=0，從a[0]開始找(a[i].L要小於0)，找到一個最大R值(Max)的線段a[Max_index]
3. left=Max_index：下次從這開始找
4. right=Max
5. 第二次一樣從left開始找(a[i].L要小於right)，找一個最大R值(Max)的線段a[Max_index]
6. 重複3~5，直到Max大於M

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct line{
	int L;
	int R;
	}a[100001];
	bool cmp(line a,line b){
	if(a.L == b.L) return a.R < b.R;
	return a.L < b.L;
	}
	int main()
	{
	int T,M;
	scanf("%d",&T);
	while (T--){
	scanf("%d",&M);
	int i,j,n=0;
	while (scanf("%d%d", &a[n].L,&a[n].R)){
	if (!a[n].L && !a[n].R) break;
	n++;
	}
	sort(a,a+n,cmp);
	int ans=0,left=0,right=0,Max=0,Max_index; //left是存a_index,right是存max
	int List[100001],l_index=0;
	bool Ans=1;
	while (Max<M){ //不斷靠近M
	right=Max;
	for(i=left;a[i].L<=right && i<n;i++){ /*a[i].L不能>right，不然範圍會沒有覆蓋*/
	if (Max<a[i].R){ //在沒有超過範圍的情況下，不斷找最靠近右邊的R
	Max=a[i].R;
	Max_index=i;
	}
	}
	if (Max==right) {Ans=0; break;} //找不到的情況
	List[l_index++]=Max_index; //將找到的點放入List
	ans++;
	left = i;
	}
	if(Ans){
	printf("%d\n",ans);
	for(i=0;i<l_index;i++)
	printf("%d %d\n",a[List[i]].L,a[List[i]].R);
	}
	else printf("0\n");
	if(T) printf("\n");
	}
	return 0;
	}

view raw [UV] 10020 Minimal Converge.cpp hosted with ❤ by GitHub