放牧代码和思想
专注自然语言处理、机器学习算法
    正处于一个非常忙的阶段,抱歉不会经常回应任何联络

POJ 2482 Stars in Your Window 题解 《挑战程序设计竞赛》

目录

POJ 2482 Stars in Your Window

数星星:夜空有n个星星,坐标(x,y)亮度c。用长W宽H的窗户去套,问能套住的星星的亮度之和的最大值?

3.6与平面和空间打交道的计算几何 

平面扫描 

引子还讲述了一理工男暗恋女神4年,到毕业都不敢约出来吃个饭的悲催故事。充分体现了广大码农的尿性,这事儿应该速战速决,因为结果事先就确定了,不取决于你有多努力。

言归正传,一开始我第一个想法是,跟《 POJ 1981 Circle and Points 》很像,不过那题是圆,而且允许点在圆上,所以不能用极限情况来操作。

换个思路,每个点能被套住的范围是有限的。将矩形抽象为一个点——矩形的中心点,则每个点能被矩形套住的范围是一个以该点为中心点,大小和原矩形一致的矩形。那么我们就得到了n个矩形,这些矩形会彼此相交,将平面分割为许多区间。为每个矩形分配亮度c作为权值,那么每个区间表示把矩形中心点放在这里,能套住的星星的亮度之和,问题转化为求解范围内的极值(RMQ)。

具体说来,将每个矩形表示为两个垂直于x轴的线段(x1,y1,y2,c)和(x2,y1,y2,-c),分别表示x坐标、下界、上界、亮度。从左往右扫描,分析线段维护线段树,也即将y1和y2区间的值加上对应的权值(或负权值),用全域最大值更新答案即可。

在实施的时候,当两条线段重合的时候,必须先处理-c那条,这样就不会将竖边框上的星星算上去了。至于横边框,也就是y值的处理,可以让线段树控制半开半闭区间[y1,y2),也可以将y2故意多减一,这样在到达边框前,亮度就已经失效了。而y1的加c虽然对自己也生效,但是题目保证没有两颗星星重合,所以y1线段也不会造成多算。

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX_N 10000
typedef long long LL;

LL xs[MAX_N];	// 横坐标
LL ys[MAX_N];	// 纵坐标
int cs[MAX_N];	// 亮度
LL X[MAX_N * 2];	// 以每个星星为中心的窗口的左右横坐标
LL Y[MAX_N * 2];	// 以每个星星为中心的窗口的上下纵坐标
pair<pair<int, int>, pair<int, int> > event[MAX_N * 2]; // (x,add),(y1,y2) 一条线段,add为亮度

////////////////////////线段树维护区域最大值/////////////////////////////////
int node_value[MAX_N * 8], node_max[MAX_N * 8];
// 将[from, to]区间的节点对应的值增加v,同时维护节点对应区域的最大值
void add(int from, int to, int v, int i, int l, int r)
{
	if (from <= l && r <= to)
	{
		node_value[i] += v;
		node_max[i] += v;
		return;
	}
	int m = (l + r) >> 1;
	if (from <= m) add(from, to, v, i * 2, l, m);
	if (m < to) add(from, to, v, i * 2 + 1, m + 1, r);
	node_max[i] = max(node_max[i * 2], node_max[i * 2 + 1]) + node_value[i];
}
////////////////////////线段树结束/////////////////////////////////////////

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n, W, H;
	while (~scanf("%d%d%d", &n, &W, &H))
	{
		for (int i = 0; i < n; ++i)
		{
			scanf("%lld%lld%d", xs + i, ys + i, cs + i);
			xs[i] *= 2;	// 乘2避免待会儿除法产生误差
			ys[i] *= 2;
		}
		for (int i = 0; i < n; ++i)
		{
			X[i * 2] = xs[i] - W;
			X[i * 2 + 1] = xs[i] + W;
			Y[i * 2] = ys[i] - H;
			Y[i * 2 + 1] = ys[i] - 1 + H;
		}
		sort(X, X + n * 2);	// 待会儿进行坐标压缩
		sort(Y, Y + n * 2);    // 为lower_bound做准备
		for (int i = 0; i < n; ++i)
		{
			event[i * 2] = make_pair(make_pair(lower_bound(X, X + n * 2, xs[i] - W) - X, cs[i]), make_pair(lower_bound(Y, Y + n * 2, ys[i] - H) - Y, lower_bound(Y, Y + n * 2, ys[i] + H - 1) - Y));
			event[i * 2 + 1] = make_pair(make_pair(lower_bound(X, X + n * 2, xs[i] + W) - X, -cs[i]), make_pair(lower_bound(Y, Y + n * 2, ys[i] - H) - Y, lower_bound(Y, Y + n * 2, ys[i] + H - 1) - Y));
		}
		sort(event, event + n * 2);
		int ans = 0;
		for (int i = 0; i < n * 2; i++)
		{	
			add(event[i].second.first, event[i].second.second, event[i].first.second, 1, 0, n * 2);
			ans = max(ans, node_max[1]);
		}
		printf("%d\n", ans);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

13892495 hankcs 2482 Accepted 1524K 141MS C++ 2431B 2015-02-16 01:09:08

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 2482 Stars in Your Window 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机