首页 > 代码库 > POJ 2482 stars in your window(线段树 , 扫描线)
POJ 2482 stars in your window(线段树 , 扫描线)
题目大意:
给你10000以内的星星的坐标和亮度,让你用一个W × H 的矩形去围住一个区域,使得区域内星星的亮度最大,矩形边缘上的星星不算。
解题思路:
对于每一个星星 建立一个(x, y , y + h , c) 的扫描线 和一个(x + w , y , y + h , - c)的扫描线,将问题转化成求区间最大值。几个需要注意的地方:矩形边缘上的需要处理一下,将每个叶节点设为长度为1的线段。另外此题如果用long long wa掉的话可以改为unsigned.
#include <iostream> #include <cstring> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstdio> #include <vector> #include <map> #include <queue> #include <stack> #include <set> #define LL unsigned #define FOR(i,x,y) for(LL i=x;i<=y;i++) #define rFor(i,x,y) for(LL i=x;i>=y;i--) #define lson l , m , rt<<1 #define rson m , r , rt<<1|1 using namespace std; const LL MAXN = 222222; LL X[MAXN<<2]; int cnt[MAXN<<2] , MAX[MAXN<<2]; struct Seg { LL h , l , r; int val; Seg() { } Seg(LL a , LL b , LL c , int d) : h(a) , l(b) , r(c) , val(d) { } bool operator < (const Seg& rhs) const { return h < rhs.h || (h == rhs.h && val < rhs.val); } }ss[MAXN]; void pushdown(int rt) { if(cnt[rt]) { cnt[rt<<1] += cnt[rt]; cnt[rt<<1|1] += cnt[rt]; MAX[rt<<1] += cnt[rt]; MAX[rt<<1|1] += cnt[rt]; cnt[rt] = 0; } } void pushup(int rt) { MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]); } void build(int l , int r , int rt) { MAX[rt] = 0 ; cnt[rt] = 0; if(l + 1 == r) return ; int m = (l + r) >> 1; build(lson); build(rson); } void update(int L , int R , int val , int l , int r , int rt) { if(L <= l && R >= r) { cnt[rt] += val; MAX[rt] += val; return ; } pushdown(rt); int m = (l + r) >> 1; if(L < m) update(L , R , val , lson); if(R > m) update(L , R , val , rson); pushup(rt); } int N , W , H; int main() { while(scanf("%d%d%d",&N , &W , &H) != EOF) { int m = 0; while(N--) { int x , y ,val; scanf("%d%d%d",&x,&y,&val); X[m] = y; ss[m++] = Seg(x , y , (LL)(y + H) , val); X[m] = (LL)(y + H); ss[m++] = Seg((LL)(x + W) , y , (LL)(y + H) ,-val); } sort(X , X + m); sort(ss , ss + m); int k = 1; for(LL i = 1 ; i < m ; i ++) if(X[i] != X[i - 1]) X[k++] = X[i]; memset(cnt , 0 , sizeof(cnt)); memset(MAX , 0 , sizeof(MAX)); build(0 , k - 1 , 1); int ans = 0; for(int i = 0 ; i < m; i++) { int l = lower_bound(X , X + k , ss[i].l) - X; int r = lower_bound(X , X + k , ss[i].r) - X ; update(l , r , ss[i].val , 0 , k - 1 , 1); ans = max(ans , MAX[1]); } printf("%d\n",ans); } return 0; }
POJ 2482 stars in your window(线段树 , 扫描线)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。