题目描述

blablabla

样例

blablabla

算法1

每个星星都能确定一个矩形。每个矩形的两条边上的权值应分别为w和-w。
所以，我们的目的是找到一个w*h的矩形，使权值最大。
线段树维护即可。反正我不会 55555.
所以我的思路是：
先把点按x从小到大排序。
那么通过枚举遍历，我们可以找到每个以i号点为左端点，宽度不超过w的最右端点j。
那么我们知道，在i到j这个区间里的点互相之间的距离是绝不会超过w的。
然后，我们在把i到j这个区间里面的点，按y排序，通过尺取的方法，找到最大权值。

时间复杂度分析：blablabla

C++ 代码

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
typedef long long ll;
typedef struct Node{
    ll x,y,w;
    Node(){};
    Node(ll a,ll b,ll c){x = a; y = b; w = c;}
}Node;

Node node[10010];
int n,w,h;

int cmpx(Node a,Node b)
{
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int cmpy(Node a,Node b)
{
    return a.y == b.y ? a.w < b.w : a.y < b.y;
}

ll max_into(int i,int j)
{
    //printf("i = %d j = %d\n",i,j);
    Node temp[30010];int top = 0;
    int x =i;
    for(i;i <= j; i ++)
        temp[++ top] = node[i];
    i = x;
    for(i; i <= j; i ++)
    {
        temp[++ top] = {node[i].x,node[i].y + h,-node[i].w};
    }

    sort(temp + 1,temp + 1 + top,cmpy);

    ll value = 0,ans = 0;
    for(int i = 1; i <= top;i ++)
    {
        if(ans < 0) ans = temp[i].w;
        else ans += temp[i].w;
        //printf("i = %d ans = %d\n",i,ans);
        value = max(value,ans);
    }
    return value;
}
int main()
{
    while(~scanf("%d%d%d",&n,&w,&h))
    {
        for(int i = 1; i <= n; i ++)
            scanf("%lld%lld%lld",&node[i].x,&node[i].y,&node[i].w);
        sort(node + 1,node + 1 + n,cmpx);
        ll ans = 0;
        for(int i = 1; i <= n;i ++)
        {
            while(i > 1 && i < n && node[i].x == node[i - 1].x) i ++;
            int j = i;
            while(j < n && node[j + 1].x - node[i].x < w) j ++;
            ans = max(ans,max_into(i,j));
        }
        printf("%lld\n",ans);
    }
}