/*
算法：离散化+暴力
	首先输入所有线段，将它的起点终点排序，得到离散化的点
	将离散化的点从头到尾走一遍，得到每条线段对应的离散点编号
	对每条线段，更新离散点的上的颜色
*/

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#define MAX 10020

struct poster{
	int start;
	int end;
}l[MAX];

int posters[MAX][2];

struct point{ //离散点
	int pos;
	int colour;  //对应的
}p[2*MAX];

int cmp(const void* a, const void* b){
	struct point*p = (struct point*)a;
	struct point*q = (struct point*)b;
	return p->pos - q->pos;
}

int n;
int colour[2*MAX]; //离散点的颜色
int used[MAX]; //出现过的海报颜色

int main(){
	int out;
	scanf("%d",&out);
	while(out--){
		memset(l,0,sizeof(l));
		memset(posters,0,sizeof(posters));
		memset(colour, -1, sizeof(colour));
		memset(used,0,sizeof(used));

		scanf("%d",&n);
		int i,counter=0;
		for(i=0; i<n; i++){
			scanf("%d%d",&posters[i][0],&posters[i][1]);
			p[counter].pos = posters[i][0];
			p[counter++].colour = -i;
			p[counter].pos = posters[i][1];
			p[counter++].colour = i;
		}
		//离散化
		qsort(p,counter,sizeof(point),cmp);
		int real_point=0;
		int last_pos = -1; //与所有点都不同
		for(i=0; i<counter; i++){
			if(last_pos != p[i].pos) real_point++, last_pos = p[i].pos;
			if(p[i].colour < 0 ) l[-p[i].colour].start = real_point-1; //离散点的编号
			else l[p[i].colour].end = real_point-1;
		}

		for(i=0; i<n; i++)
			for(int j=l[i].start; j<= l[i].end; j++)
				colour[j] = i;
		int ans=0;
		for(i=0; i<real_point; i++)
			if(!used[colour[i]]) ans++,used[colour[i]] = true;

			printf("%d\n",ans);

	}
	return 0;
}

• Re:离散化+暴力 141ms 内牛满面……（附代码及算法） (45) whoislyc 2010-08-17 20:28:20
• Re:离散化+暴力 141ms 内牛满面……（附代码及算法） (51) koma308 2010-08-26 21:04:58
  • Re:离散化+暴力 141ms 内牛满面……（附代码及算法） (94) Mghost 2010-09-07 15:42:18
• Re:离散化+暴力 141ms 内牛满面……（附代码及算法） (1693) yinger090807 2011-05-15 11:28:12