POI 2001 Intervals 區間

本文正體字版由OpenCC轉換

對於區間問題，常常使用標記開頭結尾後排序，然後掃描的方法解決問題。這道題也不例外，首先把每個區間分開看作兩個點，區間[a,b]記做a s(a爲s點),b e(b爲e點)，所有區間都這樣，然後按照在數軸上的位置排序，如果座標相同，s點放前面。從第一個點開始掃描，最初的Level爲0，遇到s點就把 Level值加1，遇到e點就把Level值減1。當處理了某個s點，如果Level變成了1，則這個點就是結果中的一個區間的左界。當處理了某個e點，如果Level變成了0，則這個點就是右界。

例如樣例給出的區間[5,6],[1,4],[10,10],[6,9],[8,10]，標記後排序，成爲 1.s 4.e 5.s 6.s 6.e 8.s 9.e 10.s 10.e 10.e 掃描到每個點的Level依次是1 0 1 2 1 2 1 2 1 0 於是結果就是[1,4],[5,10]。

掃描的時間複雜度爲O(N)，而快速排序的時間複雜度爲O(NlogN)，於是算法的總時間複雜度爲O(NlogN)。

/* 
 * Problem: POI2001 prz
 * Author: Guo Jiabao
 * Time: 2009.1.6 21:37
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAX=50001;

struct Interval
{
	int p;
	bool s;
};

int N;
Interval A[MAX*2];

int cmp (const void *a, const void *b)
{
	if ( ((Interval *)a)->p < ((Interval *)b)->p ) return -1;
	else if ( ((Interval *)a)->p > ((Interval *)b)->p ) return 1;
	else if ( ((Interval *)a)->s ) return -1;
	return 1;
}

void init()
{
	int i;
	freopen("prz.in","r",stdin);
	freopen("prz.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d",&A[i*2-1].p,&A[i*2].p);
		A[i*2-1].s=true;
		A[i*2].s=false;
	}
	N*=2;
	qsort(A+1,N,sizeof(A[0]),cmp);
}

void solve()
{
	int i,L,Level=0;
	for (i=1;i<=N;i++)
	{
		if (A[i].s)
		{
			Level++;
			if (Level==1)
				L=A[i].p;
		}
		else
		{
			Level--;
			if (Level==0)
				printf("%d %dn",L,A[i].p);
		}
	}
}

int main()
{
	init();
	solve();
	return 0;
}

<h2><span class="mw-headline">區間 </span></h2>

有一些閉區間[ai,bi]（i=1、2、…、n），找出區間數最少的表示方案，並按遞增的順序定稿輸出文件。當a≤b＜c≤d時，我們說區間[a,b]和[c,d]爲遞增順序。

任務：

你的任務是編寫一個程序完成下列工作：

從文件中讀入這些區間；
算出滿足上述條件的區間；
把結果寫入文件。

輸入：

文件的第一行是整數n，3≤n≤50000，代表區間個數，以下第i+1行1≤i≤n，有兩個用空格分開的的整數ai和bi表示一個閉區間[ai,bi]（1≤ai≤bi≤1000000）。

輸出：

文件包括，所求的不相交閉區間，每行描述一個閉區間，按照遞增順序。每個區間用兩個以空格分開的整數表示，分別是該區間的開頭和末端。

輸入樣例：
```
5
  5 6
  1 4
  10 10
  6 9
  8 10
```
輸出樣例：
```
1 4
  5 10
```

上次修改時間 2017-02-03

相關日誌