248. 窗内的星星（扫描线+尺取）

清疚 2021-11-02 10:46 131阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
题目链接：[https://www.acwing.com/problem/content/250/][https_www.acwing.com_problem_content_250]

在一个天空中有很多星星（看作平面直角坐标系），已知每颗星星的坐标和亮度（都是整数）。

求用宽为W、高为H的矩形窗户（W,H为正整数）能圈住的星星的亮度总和最大是多少。（矩形边界上的星星不算）  
输入格式

输入包含多组测试用例。

每个用例的第一行包含3个整数：n，W，H，表示星星的数量，矩形窗口的宽和高。

然后是n行，每行有3个整数：x，y，c，表示每个星星的位置（x，y）和亮度。

没有两颗星星在同一点上。  
输出格式

每个测试用例输出一个亮度总和最大值。

每个结果占一行。  
数据范围

1≤n≤10000  
,  
1≤W,H≤1000000,  
0≤x,y<231

输入样例：

3 5 4  
1 2 3  
2 3 2  
6 3 1  
3 5 4  
1 2 3  
2 3 2  
5 3 1

输出样例：

5  
6

分析：  
看到大佬们都是用线段树过的，留下了菜鸡的泪水。  
参考博客：[https://blog.csdn.net/i\_want\_to\_be\_a\_god/article/details/38621627][https_blog.csdn.net_i_want_to_be_a_god_article_details_38621627]

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

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

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/
[https_www.acwing.com_problem_content_250]: https://www.acwing.com/problem/content/250/
[https_blog.csdn.net_i_want_to_be_a_god_article_details_38621627]: https://blog.csdn.net/i_want_to_be_a_god/article/details/38621627