uva 1468 - Restaurant(贪心）

题目链接：uva 1468 - Restaurant

题目大意：有一个m*m的区域内有n个建筑，给出n个建筑的坐标，头两个位公寓，剩余的为餐馆，现在你要心开张一家饭店，要求在两个公寓的中间（即饭店要比A更接近B，比B更接近A），并且两个公寓的纵坐标相同，而且相对于任意的已经存在的餐馆来说，新的餐馆要么更接近A，要么更接近B。距离的计算为哈夫曼距离。求出满足要求的位置个数。

解题思路：首先可以确定的是满足要求的点横坐标一定在公寓AB的横坐标之间。那么遍历一遍，确定AB之间横坐标的上限值（根据已有餐馆的坐标）。然后确定各个相邻坐标之间的限制（正序逆序遍历一次，确定最小值）。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;
const int N = 1e4+5;
const int INF = 0x3f3f3f3f;
typedef long long ll;

int m, n, yMax[N*6], yMin[N*6];
int ax, ay, bx, by, py[N*6];

void init () {
	scanf("%d%d", &m, &n);
	scanf("%d%d%d%d", &ax, &ay, &bx, &by);

	if (ax > bx) swap (ax, bx);

	for (int i = ax+1; i < bx; i++) {
		yMax[i] = -INF;
		yMin[i] = INF;
	}

	int x, y;
	for (int i = 2; i < n; i++) {
		scanf("%d%d", &x, &y);

		if (y >= ay) yMin[x] = min (y, yMin[x]);
		if (y <= ay) yMax[x] = max (y, yMax[x]);
	}
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init ();

		for (int i = ax + 1; i < bx; i++)
			py[i] = min (yMin[i] - ay, ay - yMax[i]);

		py[ax] = py[bx] = 0;
		for (int i = ax + 1; i < bx; i++)
			py[i] = min (py[i], py[i-1] + 1);
		for (int i = bx - 1; i > ax; i--)
			py[i] = min (py[i], py[i+1] + 1);

		ll ans = 0;
		for (int i = ax + 1; i < bx; i++) {
			if (py[i]) {
				ans++;

				ans += min (py[i] - 1, m - ay - 1);
				ans += min (py[i] - 1, ay);
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

uva 1468 - Restaurant(贪心）,布布扣,bubuko.com

uva 1468 - Restaurant(贪心）

原文：http://blog.csdn.net/keshuai19940722/article/details/23188823