Poj2482 Stars in Your Window（扫描线）

题面

题解

下面内容引用自"李煜东《算法竞赛进阶指南》"（对原文略有缩减，侵删）：

因为矩形的大小固定，所以矩形可以由它的任意一个顶点唯一确定。我们可以考虑把矩形的右上角顶点放在什么位置，圈住的星星亮度总和最大。

所以，对于一颗星星，能够覆盖住这颗星星的右上角的位置在区间$[x,y]-[x+w,y+h]$之间，但是由于边界上的星星不算，所以不妨将星星变为$[x-0.5,y-0.5]$，于是右上角变为$[x+w-1,y+h-1]$。

问题就转化成了：平面上有若干个区域，每个区域都带有一个权值，求在哪个坐标上重叠的区域权值和最大。可以用扫描线算法来解决。

具体来说，将一颗星星抽象成一个矩形，取出左右边界（四元组）：$(x,y,y+h-1,c)$和$(x+w,y,y+h-1,-c)$，然后按照横坐标排序。关于纵坐标建立一颗线段树，维护区间最大值$dat$，初始全为$0$，线段树上的一个值$y$表示区间$[y,y+1]$，注意扫描每个四元组$(x,y_1,y_2,c)$，执行区间修改，把$[y1,y2]$中的每一个数都加$c$，用根节点$dat$更新就好了。

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::min; using std::max;

using std::swap; using std::sort;

using std::unique; using std::lower_bound;

typedef long long ll;

#define int ll

template<typename T>

void read(T &x) {

    int flag = 1; x = 0; char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int N = 2e4 + 10;

ll n, W, H;

ll cf[N << 1], tot;

struct star { ll x, y, h; } s[N];

struct raw { ll x, y1, y2, d; } cy[N << 1]; int cnt;

inline bool cmp (const raw &a ,const raw &b) { return a.x < b.x || (a.x == b.x && a.d < b.d); }

ll val[N << 4], add[N << 4];

void pushdown(int o, int lc, int rc) {

	if(add[o]) {

		add[lc] += add[o], add[rc] += add[o];

		val[lc] += add[o], val[rc] += add[o], add[o] = 0;

	}

}

void modify (int ml, int mr, ll k, int o = 1, int l = 1, int r = tot) {

	if(l >= ml && r <= mr) { val[o] += k, add[o] += k; return ; }

	int mid = (l + r) >> 1, lc = o << 1, rc = lc | 1;

	pushdown(o, lc, rc);

	if(ml <= mid) modify(ml, mr, k, lc, l, mid);

	if(mr > mid) modify(ml, mr, k, rc, mid + 1, r);

	val[o] = max(val[lc], val[rc]);

}

signed main () {

	while(scanf("%lld%lld%lld", &n, &W, &H) != EOF) {

		cnt = tot = 0; ll ans = 0;

		for(int i = 1; i <= n; ++i) {

			read(s[i].x), read(s[i].y), read(s[i].h);

			cy[++cnt] = (raw){s[i].x, s[i].y, s[i].y + H - 1, s[i].h};

			cy[++cnt] = (raw){s[i].x + W, s[i].y, s[i].y + H - 1, -s[i].h};

			cf[++tot] = s[i].y, cf[++tot] = s[i].y + H - 1;

		} sort(&cf[1], &cf[tot + 1]), tot = unique(&cf[1], &cf[tot + 1]) - cf - 1;

		sort(&cy[1], &cy[cnt + 1], cmp);

		memset(val, 0, sizeof val), memset(add, 0, sizeof add);

		for(int i = 1; i <= cnt; ++i) {

			cy[i].y1 = lower_bound(&cf[1], &cf[tot + 1], cy[i].y1) - cf;

			cy[i].y2 = lower_bound(&cf[1], &cf[tot + 1], cy[i].y2) - cf;

			modify(cy[i].y1, cy[i].y2, cy[i].d);

			ans = max(ans, val[1]);

		}

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

	}

	return 0;

}

巴特西

Poj2482 Stars in Your Window（扫描线）

题面

题解

最新文章

热门文章