CODE[VS] 天梯 1214 線段覆蓋

2019-11-10 20:18:59

字體：大中小

來源：轉載

供稿：網友

線段覆蓋 時間限制: 1 s 空間限制: 128000 KB 題目等級 : 黃金 Gold

題解

題目描述 Description

給定x軸上的N（0<N<100）條線段，每個線段由它的二個端點a_I和b_I確定，I=1,2,……N.這些坐標都是區間（－999，999）的整數。有些線段之間會相互交疊或覆蓋。請你編寫一個程序，從給出的線段中去掉盡量少的線段，使得剩下的線段兩兩之間沒有內部公共點。所謂的內部公共點是指一個點同時屬于兩條線段且至少在其中一條線段的內部（即除去端點的部分）

輸入描述 Input Description

輸入第一行是一個整數N。接下來有N行，每行有二個空格隔開的整數，表示一條線段的二個端點的坐標

。

輸出描述 Output Description

輸出第一行是一個整數表示最多剩下的線段數。

樣例輸入 Sample Input

6 3

1 3

2 5

樣例輸出 Sample Output

數據范圍及提示 Data Size & Hint

0<N<100

思路：

貪心。我的方法是，從小到大開始遍歷區間，如果下一個區間在前一個內，那么left和right設置成這次的小區間并n–；如果下一個區間和前一個區間相交叉，那么摒棄這次的。即left和right不變，只n–。其中right剛開始要設置初值為-1，表示找到第一個區間，left和right設置為此區間，然后進行和下一個區間比較。

代碼：

#include<iostream>#include<string.h>#include<math.h>#include<algorithm>#include<stdio.h> using namespace std;struct Fo{ int y; struct Fo *next;};int main(){ struct Fo *p[2010];//以結構體角標為線段左端點，結構體元素y為右端點 int n; scanf("%d", &n); for (int i = 2; i<2010; i++){ p[i] = new Fo; p[i]->next = NULL; } for (int i = 1; i <= n; i++){ int a, b; scanf("%d %d", &a, &b); a += 1000;//題目要求(-999,999)所以加上1000排除負角標 b += 1000; if(a>b){a ^= b;b ^= a;a ^= b;}//a和b進行交換 struct Fo *q = p[a]; while (q->next)q = q->next;//賦值操作 q->next = new Fo; q->next->y = b; q->next->next = NULL; } int left, right=-1;//初始化-1 for (int i = 2; i < 2010; i++){ struct Fo *q = p[i]->next; while (q){ if (i<right){//這里兩種情況，一種i在此時最大區間左邊，或者右邊。如果右邊,那肯定不會相交. if (q->y <= right){ left = i; right = q->y; } n--; }else{ left = i; right = q->y; } q = q->next; } }