CODE[VS] 天梯 1214 線段覆蓋

2019-11-10 18:08:03

字體：大中小

供稿：網(wǎng)友

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

題解

題目描述 Description

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

輸入描述 Input Description

輸入第一行是一個整數(shù)N。接下來有N行，每行有二個空格隔開的整數(shù)，表示一條線段的二個端點(diǎn)的坐標(biāo)

。

輸出描述 Output Description

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

樣例輸入 Sample Input

6 3

1 3

2 5

樣例輸出 Sample Output

數(shù)據(jù)范圍及提示 Data Size & Hint

0<N<100

思路：

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

代碼：

#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];//以結(jié)構(gòu)體角標(biāo)為線段左端點(diǎn)，結(jié)構(gòu)體元素y為右端點(diǎn) 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排除負(fù)角標(biāo) b += 1000; if(a>b){a ^= b;b ^= a;a ^= b;}//a和b進(jìn)行交換 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在此時最大區(qū)間左邊，或者右邊。如果右邊,那肯定不會相交. if (q->y <= right){ left = i; right = q->y; } n--; }else{ left = i; right = q->y; } q = q->next; } }