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.

【题解】

【代码】

[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);
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);
}