2244.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2244 on 2006-08-25 at 20:32:33 */ 
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
 
typedef unsigned int uint;
const int CN = 1024;
const int PN = 10240;
 
bool capp[CN];
int cn;
 
class Point {
public:
	int x, c;
	void make();
	bool operator <(const Point& p) const { return x < p.x; }
};
void Point::make() {
	scanf("%d %d", &x, &c);
	if(!capp[c]) { capp[c] = true; cn++; }
}
 
int main()
{
	int n, i, cnt[CN];
	Point p[PN];
	
	while(scanf("%d", &n) != EOF) {
		memset(capp, false, sizeof(capp)); cn = 0;
		for(i = 0; i < n; i++) p[i].make();
		sort(p, p+n);
		int cp = 0, b = 0, e;
		uint dis = UINT_MAX;
		memset(cnt, 0, sizeof(cnt));
		for(e = 0; e < n; e++) {
			if(cnt[p[e].c] == 0) cp++;
			cnt[p[e].c]++;
			while(cnt[p[b].c] != 1) { cnt[p[b].c]--; b++; }
			if(cp == cn) dis = min(dis, (uint)(p[e].x-p[b].x));
		}
		printf("%u\n", dis);
	}
	
	return 0;
}