首页 > ACM题库 > HDU-杭电 > HDU 3845-Mummy Madness[解题报告]HOJ
2015
04-13

HDU 3845-Mummy Madness[解题报告]HOJ

Mummy Madness

问题描述 :

During an excursion to the desert at the 2011 ACM-ICPC World Finals, you come across an old Egyptian tomb. Unfortunately, opening the tomb turns out to be a bad idea: all of a sudden, what was just a few moments ago an empty desert has now become a desert crawling with grumpy mummies (you would be grumpy too if you were suddenly awakened after a few thousand years of peaceful sleep).(Fortunately, after solving this problem, you woke up safe and sound in a hotel room in Florida. The enraged mummies had just been a dream.
Or had they?)
Mining Your Own Business

输入:

The input consists of several test cases. Each test case begins with an integer n (0 <= n <= 10^5) giving the number of mummies in the desert. The following n lines each contain two integers x and y, indicating that there is initially a mummy at coordinates (x, y) of the desert, where x and y are both bounded by 10^6 in absolute value. Your starting position is (0, 0), and no mummy starts at this position.

The last test case is followed by a line containing the number &#1048576;1.

输出:

The input consists of several test cases. Each test case begins with an integer n (0 <= n <= 10^5) giving the number of mummies in the desert. The following n lines each contain two integers x and y, indicating that there is initially a mummy at coordinates (x, y) of the desert, where x and y are both bounded by 10^6 in absolute value. Your starting position is (0, 0), and no mummy starts at this position.

The last test case is followed by a line containing the number &#1048576;1.

样例输入:

4
-3 5
3 4
-6 -2
1 -5
1
0 -1
-1

样例输出:

Case 1: 4
Case 2: never

#include <cstdio>
#include <cstring>
#include <algorithm>

#define PI pair<int, int>
#define MP make_pair
#define x first
#define y second

const int maxn = 100100;

using namespace std;

int N, m;
inline bool in( int x, int y )
{
	return x >= -m && x <= m && y >= -m && y <= m;
}

PI p[maxn];
PI a[maxn], b[maxn], c[maxn], d[maxn];
int ea, eb, ec, ed;

bool chk()
{
	int i, j, k;

	ea = eb = ec = ed = -1;
	for( i = 0; i < N; ++i )
	{
		if( in(p[i].x+m, p[i].y-m) )
		{
			while( ea >= 0 && a[ea].y >= p[i].y-m )	ea--;
			if( ea >= 0 && a[ea].x==p[i].x+m )	continue;
			a[++ea] = MP(p[i].x+m, p[i].y-m);
		}
		if( in(p[i].x+m, p[i].y+m) )
		{
			while( eb >= 0 && b[eb].y <= p[i].y+m )	eb--;
			if( eb >= 0 && b[eb].x==p[i].x+m )	continue;
			b[++eb] = MP(p[i].x+m, p[i].y+m);
		}
	}
	for( i = N-1; i >= 0; --i )
	{
		if( in(p[i].x-m, p[i].y-m) )
		{
			while( ec >= 0 && c[ec].y >= p[i].y-m )	ec--;
			if( ec >= 0 && c[ec].x==p[i].x-m )	continue;
			c[++ec] = MP(p[i].x-m, p[i].y-m);
		}
		if( in(p[i].x-m, p[i].y+m) )
		{
			while( ed >= 0 && d[ed].y <= p[i].y+m )	ed--;
			if( ed >= 0 && d[ed].x==p[i].x-m )	continue;
			d[++ed] = MP(p[i].x-m, p[i].y+m);
		}
	}

	int na = 0, nb = 0, nc = ec+1, nd = ed+1;
	int v1, v2;
	for( i = -m; i <= m; ++i )
	{
		if( nc > 0 && c[nc-1].x == i )	nc--;
		if( nd > 0 && d[nd-1].x == i )	nd--;

		v1 = m+1, v2 = -m-1;

		if( na <= ea )	v1 = min(v1, a[na].y);
		if( nb <= eb )	v2 = max(v2, b[nb].y);
		if( nc <= ec )	v1 = min(v1, c[nc].y);
		if( nd <= ed )	v2 = max(v2, d[nd].y);

		if( v1-1 > v2 )	return 0;
	
		if( na <= ea && a[na].x == i )	na++;
		if( nb <= eb && b[nb].x == i )	nb++;
	}

	return 1;
}

int main()
{
	int i, j, k, cases = 1;
	int ll, rr;

	while( scanf("%d", &N), N+1 )
	{
		for( i = 0; i < N; ++i )
			scanf("%d %d", &p[i].x, &p[i].y);
		sort(p, p+N);

		ll = -1, rr = 1000000;
		while( rr-ll > 1 )
		{
			m = (ll+rr)/2;
			if( chk() )
				rr = m;
			else
				ll = m;
		}

		m = rr;
		printf("Case %d: ", cases++);
		if( chk() )	printf("%d\n", rr);
		else	puts("never");
	}

	return 0;
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。