線(xiàn)段覆蓋 時(shí)間限制: 1 s 空間限制: 128000 KB 題目等級(jí) : 黃金 Gold
題解
題目描述 Description
給定x軸上的N（0<N<100）條線(xiàn)段，每個(gè)線(xiàn)段由它的二個(gè)端點(diǎn)a_I和b_I確定，I=1,2,……N.這些坐標(biāo)都是區(qū)間（－999，999）的整數(shù)。有些線(xiàn)段之間會(huì)相互交疊或覆蓋。請(qǐng)你編寫(xiě)一個(gè)程序，從給出的線(xiàn)段中去掉盡量少的線(xiàn)段，使得剩下的線(xiàn)段兩兩之間沒(méi)有內(nèi)部公共點(diǎn)。所謂的內(nèi)部公共點(diǎn)是指一個(gè)點(diǎn)同時(shí)屬于兩條線(xiàn)段且至少在其中一條線(xiàn)段的內(nèi)部（即除去端點(diǎn)的部分）
輸入描述 Input Description
輸入第一行是一個(gè)整數(shù)N。接下來(lái)有N行，每行有二個(gè)空格隔開(kāi)的整數(shù)，表示一條線(xiàn)段的二個(gè)端點(diǎn)的坐標(biāo)
。
輸出描述 Output Description
輸出第一行是一個(gè)整數(shù)表示最多剩下的線(xiàn)段數(shù)。
樣例輸入 Sample Input
3
6 3
1 3
2 5
樣例輸出 Sample Output
2
數(shù)據(jù)范圍及提示 Data Size & Hint
0<N<100
思路：
貪心。我的方法是，從小到大開(kāi)始遍歷區(qū)間，如果下一個(gè)區(qū)間在前一個(gè)內(nèi)，那么left和right設(shè)置成這次的小區(qū)間并n–；如果下一個(gè)區(qū)間和前一個(gè)區(qū)間相交叉，那么摒棄這次的。即left和right不變，只n–。 其中right剛開(kāi)始要設(shè)置初值為-1，表示找到第一個(gè)區(qū)間，left和right設(shè)置為此區(qū)間，然后進(jìn)行和下一個(gè)區(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)為線(xiàn)段左端點(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在此時(shí)最大區(qū)間左邊，或者右邊。如果右邊,那肯定不會(huì)相交. if (q->y <= right){ left = i; right = q->y; } n--; }else{ left = i; right = q->y; } q = q->next; } }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
