题目链接:poj 2482 Stars in Your Window
题目大意:平面上有N个星星,问一个W∗H的矩形最多能括进多少个星星。
解题思路:扫描线的变形。只要以每个点为左上角,建立矩形,这个矩形即为框框左下角放的位置可以括到该点,那么N个星星就有N个矩形,扫描线处理哪些位置覆盖次数最多。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 40000;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2];
ll v[maxn << 2], s[maxn << 2];
inline void pushup (int u) {
s[u] = max(s[lson(u)], s[rson(u)]) + v[u];
}
inline void maintain (int u, int d) {
v[u] += d;
pushup(u);
}
void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
v[u] = s[u] = 0;
if (l == r)
return;
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
}
void modify (int u, int l, int r, int d) {
if (l <= lc[u] && rc[u] <= r) {
maintain(u, d);
return;
}
int mid = (lc[u] + rc[u]) / 2;
if (l <= mid)
modify(lson(u), l, r, d);
if (r > mid)
modify(rson(u), l, r, d);
pushup(u);
}
struct Seg {
ll x, l, r, d;
Seg (ll x = 0, ll l = 0, ll r = 0, ll d = 0) {
this->x = x;
this->l = l;
this->r = r;
this->d = d;
}
friend bool operator < (const Seg& a, const Seg& b) {
return a.x < b.x;
}
};
int N, W, H;
vector<ll> pos;
vector<Seg> vec;
inline int find (ll k) {
return lower_bound(pos.begin(), pos.end(), k) - pos.begin();
}
void init () {
ll x, y, d;
pos.clear();
vec.clear();
for (int i = 0; i < N; i++) {
scanf("%lld%lld%lld", &x, &y, &d);
pos.push_back(y - H);
pos.push_back(y);
vec.push_back(Seg(x - W, y - H, y, d));
vec.push_back(Seg(x, y - H, y, -d));
}
sort(pos.begin(), pos.end());
sort(vec.begin(), vec.end());
}
ll solve () {
ll ret = 0;
build (1, 0, pos.size());
for (int i = 0; i < vec.size(); i++) {
modify(1, find(vec[i].l), find(vec[i].r) - 1, vec[i].d);
ret = max(ret, s[1]);
}
return ret;
}
int main () {
while (scanf("%d%d%d", &N, &W, &H) == 3) {
init();
printf("%lld\n", solve());
}
return 0;
}
分享到:
相关推荐
poj 2482 Stars in Your Window.md
以每个星星为中心,得到可以罩住它的矩形的左下角的范围,这些范围内的点增加星星亮度,由于落在框上的点不算...一根横线从下向上扫描,遇到矩形下边将对应x范围都加亮度,上边框减亮度。每次用线段树更新和求最大值。
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
北大POJ3007-Organize Your Train part II 解题报告+AC代码
北大POJ1936-All in All 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
poj 3763 Tour in Wonder Land.md
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2388-Who's in the Middle 解题报告+AC代码
POJ上的一道题,我感觉挺难的。分享给大家,这是利用拓扑排序实现,也算是拓扑排序的一道例题。有助于大家对拓排的理解
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
我的博客链接:http://blog.csdn.net/CABI_ZGX
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告