遇见poj上最浪漫的题目。。题目里图片以上几百词为一篇模板级英文情书。这情感和细腻的文笔深深地打动了我。。不会写情书的童鞋速度进来学习。传送门
题意:坐标系内有n个星星,每个星星都有一个亮度c (1<= c <= 100),坐标和亮度都已给出。 有一个矩形的窗户(就是个理想化的矩形),四条边与x轴或y轴平行。矩形可以在坐标系内平移,但不可以进行旋转操作。求这个矩形可以框住的星星的亮度之和最大为多少。注意:恰好在边上的星星不算在内。
思路:好吧,这题又是看别人的题解才做出来的,深深自责中。。。思路最主要也是最难想的地方就是,题目中是用矩形框住星星,在实际求解过程中要转化为对于每一颗星星,先找出能框住它的那些矩形(肯定不止一个)在坐标系内能够覆盖的区域。因为矩形可以平移,有无数中情况,但是极限情况就四种,就是星星位于矩形的四个顶点的情况。可以想象出,总区域该是四个矩形构成的一个大矩形。将这个矩形通过某种操作,覆盖上该星星的亮度c。最后的问题就转化为了,求坐标系内覆盖的亮度最大的矩形。这就转化到了用线段树扫描法求矩形面积的问题上了。
但实际解题过程中,只需要考虑星星位于矩形一个顶点时的情况(这里我也有些迷迷糊糊的,我的理解是,对于最后求得的结果,位于四个顶点的情况是等价的。可以想想最后得到的那个矩形里分布着不均匀的星星,可能对于某星星,这个矩形能够通过位于右上角顶点的情况计算出;对于另一个星星,可能就是右下角的情况了,所以从哪个顶点算都一样),这样处理起来也特别简单。
思路核心部分:题目中给出的矩形窗户的长为w,宽为h。现对于每一个星星(x, y),都想象一个以它为左下角顶点且长为w,宽为h的矩形。由于位于矩形边上的星星不算。因此这颗星星实际可以作用到的范围,x轴方向为[x, x+w),y轴方向为[y, y+h)。如果通过自下往上的扫描法,可以沿x轴建线段树,使用cover维护x轴区间内覆盖的亮度,使用tmax维护x轴区间内亮度的最大值。当扫描到一颗星星时,就将一条两端点分别为x, x+w-1(之所以减一,是因为线段树每个叶子表示的区间为该点到下一点之间的区间。),纵坐标为y,权值flag为该星星的亮度c的一条边覆盖到x轴上。但线继续朝上扫描时,当扫描到纵坐标为y+h时,该星星的亮度就不再起作用了。因此,对于每一颗星星,在坐标系内我们还要假象一条边,两端点为x, x+w-1,纵坐标为y+h,权值flag为-c。这样当扫描线到了y+h的高度时,将这条边覆盖到x轴上,便将之前的那条边给抵消了!
这样每往x轴上覆盖一条边,通过线段树维护数据,计算出当前x轴上存在的亮度和的最大值(可以肯定,一定存在一个长为w,宽为h的矩形,它框住的星星亮度和为此时计算出的亮度和最大值),若最大值大于ans,则赋值给ans。最后ans即为结果。
后话:因为x,y的坐标大小可达2^31,因此离散化是必须的。还有,x+w的范围可能超2^31,用int会wa,改成long long就ok了。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #define maxn 22222 5 #define lson l, m, rt << 1 6 #define rson m + 1, r, rt << 1 | 1 7 using namespace std; 8 int cover[maxn<<2], tmax[maxn<<2]; 9 long long x[maxn]; 10 struct seg 11 { 12 long long l, r, h; 13 int flag; 14 seg() {} 15 seg(long long x1,long long x2,long long y,int s) : l(x1), r(x2), h(y), flag(s) {} 16 bool operator < (const seg &cmp) const 17 { 18 if (h == cmp.h) return flag < cmp.flag; 19 return h < cmp.h; 20 } 21 }ss[maxn]; 22 int bin(long long key,int len,long long x[]) 23 { 24 int l = 0, r = len - 1; 25 while (l <= r) 26 { 27 int m = (l + r) >> 1; 28 if (key == x[m]) return m; 29 else if (key < x[m]) r = m - 1; 30 else l = m + 1; 31 } 32 return -1; 33 } 34 void PushDown(int rt) 35 { 36 if (cover[rt] != 0) 37 { 38 cover[rt<<1] += cover[rt]; 39 cover[rt<<1|1] += cover[rt]; 40 tmax[rt<<1] += cover[rt]; 41 tmax[rt<<1|1] += cover[rt]; 42 cover[rt] = 0; 43 } 44 } 45 void PushUp(int rt) 46 { 47 tmax[rt] = max(tmax[rt<<1], tmax[rt<<1|1]); 48 } 49 void update(int L,int R,int c,int l,int r,int rt) 50 { 51 if (L <= l && r <= R) 52 { 53 cover[rt] += c; 54 tmax[rt] += c; 55 return; 56 } 57 PushDown(rt); 58 int m = (l + r) >> 1; 59 if (L <= m) update(L, R, c, lson); 60 if (m < R) update(L, R, c, rson); 61 PushUp(rt); 62 } 63 int main() 64 { 65 int n, w, h; 66 //freopen("data.in", "r", stdin); 67 while (~scanf("%d%d%d",&n,&w,&h)) 68 { 69 int tot = 0; 70 long long xi, y; 71 int c; 72 memset(cover, 0, sizeof(cover)); 73 memset(tmax, 0, sizeof(cover)); 74 for (int i = 0; i < n; i++) 75 { 76 scanf("%lld%lld%d",&xi,&y,&c); 77 x[tot] = xi; 78 ss[tot++] = seg(xi, xi + w, y, c); 79 x[tot] = xi + w; 80 ss[tot++] = seg(xi, xi + w, y + h, -c); 81 } 82 sort(x, x + tot); 83 sort(ss, ss + tot); 84 int k = 1; 85 for (int i = 1; i < tot; i++) 86 if (x[i] != x[i-1]) x[k++] = x[i]; 87 int ans = 0; 88 for (int i = 0; i < tot - 1; i++) 89 { 90 int l = bin(ss[i].l, k, x); 91 int r = bin(ss[i].r, k, x) - 1; 92 if (l <= r) update(l, r, ss[i].flag, 0, k - 1, 1); 93 if (ans < tmax[1]) ans = tmax[1]; 94 } 95 printf("%d\n",ans); 96 } 97 return 0; 98 }