频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
线段树典型例题--poj2482
2012-07-24 11:30:47           
收藏   我要投稿

【题意】

Assume the sky is a flat plane. All the stars lie on it with a location (x, y). for each star, there is a grade ranging from 1 to 100, representing its brightness, where 100 is the brightest and 1 is the weakest. The window is a rectangle whose edges are parallel to the x-axis or y-axis. Your task is to tell where I should put the window in order to maximize the sum of the brightness of the stars within the window. Note, the stars which are right on the edge of the window does not count. The window can be translated but rotation is not allowed.

There are at least 1 and at most 10000 stars in the sky. 1<=W,H<=1000000, 0<=x,y<2^31.

【题解】

首先是离散化+扫描线,但线段树如何维护?

将星星拆成两个,(x[i],y[i],light[i])和(x[i],y[i]+h,-light[i]),然后维护两个量,sum和maxsum。sum是前缀和,maxsum是最大的前缀和

具体维护看代码

【代码】


[cpp] 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <algorithm> 
using namespace std; 
 
const int N=10005; 
 
struct node 

    int x,y,idx1,idx2,c; 
}a[N]; 
 
int ss[N*10],ms[N*10]; 
long long g[N*3]; 
 
void ins(int i,int l,int r,int x,int cc) 

    if (l==r) 
    { 
        ss[i]+=cc; 
        ms[i]+=cc; 
        return; 
    } 
    int mid=(l+r)/2; 
    if (x<=mid) ins(i*2,l,mid,x,cc); 
    else ins(i*2+1,mid+1,r,x,cc); 
    ss[i]=ss[i*2]+ss[i*2+1]; 
    ms[i]=max(max(ms[i*2],ss[i*2]+ms[i*2+1]),ss[i*2]); 

 
bool cmp(node a,node b) 

    return a.x<b.x || (a.x==b.x && a.y<b.y); 

 
int main() 

    int tot,xl,xr,i,tmp,n,w,h,ans; 
 
    freopen("in2","r",stdin); 
    while (scanf("%d%d%d",&n,&w,&h)!=EOF) 
    { 
        memset(ss,0,sizeof(ss)); 
        memset(ms,0,sizeof(ms)); 
        tot=ans=0; 
        for (i=0;i<n;i++) 
        { 
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c); 
            g[tot++]=a[i].y; 
            g[tot++]=(long long)a[i].y+h; 
        } 
        sort(g,g+tot); 
        tot=unique(g,g+tot)-g; 
        sort(a,a+n,cmp); 
        for (i=0;i<n;i++) 
        { 
            a[i].idx1=lower_bound(g,g+tot,a[i].y)-g+1; 
            a[i].idx2=lower_bound(g,g+tot,(long long)a[i].y+h)-g+1; 
        } 
        xl=xr=0; 
        while (xr<n && a[xr].x-a[xl].x<w) 
        { 
            ins(1,1,tot,a[xr].idx1,a[xr].c); 
            ins(1,1,tot,a[xr].idx2,-a[xr].c); 
            xr++; 
        } 
        xr--; 
        while (xl<=xr) 
        { 
            ans=max(ans,ms[1]); 
            tmp=xl; 
            while (xl<=xr && a[xl].x==a[tmp].x) 
            { 
                ins(1,1,tot,a[xl].idx1,-a[xl].c); 
                ins(1,1,tot,a[xl].idx2,a[xl].c); 
                xl++; 
            } 
            while (xr+1<n && a[xr+1].x-a[xl].x<w) 
            { 
                xr++; 
                ins(1,1,tot,a[xr].idx1,a[xr].c); 
                ins(1,1,tot,a[xr].idx2,-a[xr].c); 
            } 
        }   www.2cto.com
        printf("%d\n",ans); 
    } 

 

作者:ascii991
点击复制链接 与好友分享!回本站首页
相关TAG标签 线段 例题 典型
上一篇:基于策略模式的定制new和delete
下一篇: HDOJ 2066 一个人的旅游
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站