热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

POJ2482星空中的星星:利用线段树与扫描线算法解决

在《POJ2482星空中的星星》问题中,通过运用线段树和扫描线算法,可以高效地解决星星在窗口内的计数问题。该方法不仅能够快速处理大规模数据,还能确保时间复杂度的最优性,适用于各种复杂的星空模拟场景。
Stars in Your Window
 

Description

 

Fleeting time does not blur my memory of you. Can it really be 4 years since I first saw you? I still remember, vividly, on the beautiful Zhuhai Campus, 4 years ago, from the moment I saw you smile, as you were walking out of the classroom and turned your head back, with the soft sunset glow shining on your rosy cheek, I knew, I knew that I was already drunk on you. Then, after several months’ observation and prying, your grace and your wisdom, your attitude to life and your aspiration for future were all strongly impressed on my memory. You were the glamorous and sunny girl whom I always dream of to share the rest of my life with. Alas, actually you were far beyond my wildest dreams and I had no idea about how to bridge that gulf between you and me. So I schemed nothing but to wait, to wait for an appropriate opportunity. Till now — the arrival of graduation, I realize I am such an idiot that one should create the opportunity and seize it instead of just waiting. 

These days, having parted with friends, roommates and classmates one after another, I still cannot believe the fact that after waving hands, these familiar faces will soon vanish from our life and become no more than a memory. I will move out from school tomorrow. And you are planning to fly far far away, to pursue your future and fulfill your dreams. Perhaps we will not meet each other any more if without fate and luck. So tonight, I was wandering around your dormitory building hoping to meet you there by chance. But contradictorily, your appearance must quicken my heartbeat and my clumsy tongue might be not able to belch out a word. I cannot remember how many times I have passed your dormitory building both in Zhuhai and Guangzhou, and each time aspired to see you appear in the balcony or your silhouette that cast on the window. I cannot remember how many times this idea comes to my mind: call her out to have dinner or at least a conversation. But each time, thinking of your excellence and my commonness, the predominance of timidity over courage drove me leave silently. 

Graduation, means the end of life in university, the end of these glorious, romantic years. Your lovely smile which is my original incentive to work hard and this unrequited love will be both sealed as a memory in the deep of my heart and my mind. Graduation, also means a start of new life, a footprint on the way to bright prospect. I truly hope you will be happy everyday abroad and everything goes well. Meanwhile, I will try to get out from puerility and become more sophisticated. To pursue my own love and happiness here in reality will be my ideal I never desert. 

Farewell, my princess! 

If someday, somewhere, we have a chance to gather, even as gray-haired man and woman, at that time, I hope we can be good friends to share this memory proudly to relight the youthful and joyful emotions. If this chance never comes, I wish I were the stars in the sky and twinkling in your window, to bless you far away, as friends, to accompany you every night, sharing the sweet dreams or going through the nightmares together. 
技术分享

Here comes the problem: 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. 

Input

 

There are several test cases in the input. The first line of each case contains 3 integers: n, W, H, indicating the number of stars, the horizontal length and the vertical height of the rectangle-shaped window. Then n lines follow, with 3 integers each: x, y, c, telling the location (x, y) and the brightness of each star. No two stars are on the same point. 

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

Output

 

For each test case, output the maximum brightness in a single line.

Sample Input

 

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

Sample Output

 

5
6

 

题意:

  给你一个w*h的矩形,和平面上n个点,每个点有权值

  问你用这个矩形能框住最大的点权和,要球必须在这个矩形内部

题解:

  将点的范围延展成矩形,用扫描线去扫

  线段树维护区间最值

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 2e6+20, M = 1e6+10, mod = 1e9+7, inf = 2e9+1000;
typedef long long ll;

int n,w,h;
ll y[N];
struct Line{
    ll top,x,down,f;
    Line() {}
    Line ( ll a,ll b,ll c,ll d )  { top=a,x=b,down=c,f=d;}
}line[N];
bool cmp(Line s1,Line s2) {
    if(s1.x==s2.x) return s1.f<s2.f;
    else return s1.x<s2.x;
}
mapint > H;
ll mx[N*4],l[N*4],r[N*4],lazy[N*4];
void pushdown(int k) {
    if(lazy[k]==0) return ;
    ll tmp = lazy[k];
    lazy[k] = 0;
    mx[k<<1]+=tmp;
    mx[k<<1|1]+=tmp;
    lazy[k<<1] += tmp;
    lazy[k<<1|1] += tmp;
}
void build(int k,int s,int t) {
    l[k] = s;
    r[k] = t;
    mx[k] = 0;
    lazy[k] = 0;
    if(s==t) return ;
    int mid = (s+t)>>1;
    build(k<<1,s,mid);
    build(k<<1|1,mid+1,t);
}
void update(int k,int x,int y,ll c) {
     pushdown(k);
    if(l[k]==x&&r[k]==y) {
        mx[k] += c;
        lazy[k] += c;
        return ;
    }

    int mid = (l[k]+r[k])>>1;
    if(y<=mid) update(k<<1,x,y,c);
    else if(x>mid) update(k<<1|1,x,y,c);
    else update(k<<1,x,mid,c),update(k<<1|1,mid+1,y,c);

    mx[k] = max(mx[k<<1],mx[k<<1|1]);
}
int main() {
    while(scanf("%d%d%d",&n,&w,&h)!=EOF) {
        int cnt = 0;
         H.clear();

        for(int i=1;i<=n;i++) {
            ll a,b,c;
            scanf("%I64d%I64d%I64d",&a,&b,&c);
            line[++cnt] = Line(b+h-1,a,b,c);
            y[cnt] = b;
            line[++cnt] = Line(b+h-1,a+w,b,-c);
            y[cnt] = b+h-1;
        }

        sort(y+1,y+cnt+1);
        sort(line+1,line+1+cnt,cmp);
        int c = unique(y+1,y+cnt+1) - y - 1;
        for(int i=1;i<=c;i++) H[y[i]] = i;

        build(1,1,c);
        ll ans = 0;
        for(int i=1;i<=cnt;i++) {
            update(1,H[line[i].down],H[line[i].top],line[i].f);
            ans = max(ans,mx[1]);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

POJ 2482 Stars in Your Window 线段树扫描线


推荐阅读
  • 本文介绍了如何通过C#语言调用动态链接库(DLL)中的函数来实现IC卡的基本操作,包括初始化设备、设置密码模式、获取设备状态等,并详细展示了将TextBox中的数据写入IC卡的具体实现方法。 ... [详细]
  • 本文将从基础概念入手,详细探讨SpringMVC框架中DispatcherServlet如何通过HandlerMapping进行请求分发,以及其背后的源码实现细节。 ... [详细]
  • importjava.io.*;importjava.util.*;publicclass五子棋游戏{staticintm1;staticintn1;staticfinalintS ... [详细]
  • 解决Visual Studio Code中PHP Intelephense误报问题
    PHP作为一种高度灵活的编程语言,其代码结构可能导致Intelephense插件在某些情况下报告不必要的错误或警告。自1.3.3版本起,Intelephense引入了多个配置选项,允许用户根据具体的工作环境和编程风格调整这些诊断信息的显示。 ... [详细]
  • 嵌套列表的扁平化处理
    本文介绍了一种方法,用于遍历嵌套列表中的每个元素。如果元素是整数,则将其添加到结果数组中;如果元素是一个列表,则递归地遍历这个列表。此方法特别适用于处理复杂数据结构中的嵌套列表。 ... [详细]
  • 本文详细探讨了BCTF竞赛中窃密木马题目的解题策略,重点分析了该题目在漏洞挖掘与利用方面的技巧。 ... [详细]
  • SQL Server 存储过程实践任务(第二部分)
    本文档详细介绍了三个SQL Server存储过程的创建与使用方法,包括统计特定类型客房的入住人数、根据房间号查询客房详情以及删除特定类型的客房记录。 ... [详细]
  • 在编程实践中,正确管理和释放资源是非常重要的。本文将探讨 Python 中的 'with' 关键字及其背后的上下文管理器机制,以及它们如何帮助我们更安全、高效地管理资源。 ... [详细]
  • 材料光学属性集
    材料光学属性集概述了材料在不同光谱下的光学行为,包括可见光透射率、太阳光透射率等关键参数。 ... [详细]
  • 本文详细介绍了JQuery Mobile框架中特有的事件和方法,帮助开发者更好地理解和应用这些特性,提升移动Web开发的效率。 ... [详细]
  • 本文详细介绍了C++中的构造函数,包括其定义、特点以及如何通过构造函数进行对象的初始化。此外,还探讨了转换构造函数的概念及其在不同情境下的应用,以及如何避免不必要的隐式类型转换。 ... [详细]
  • 本文详细介绍了iOS应用的生命周期,包括各个状态及其转换过程中的关键方法调用。 ... [详细]
  • Windows操作系统提供了Encrypting File System (EFS)作为内置的数据加密工具,特别适用于对NTFS分区上的文件和文件夹进行加密处理。本文将详细介绍如何使用EFS加密文件夹,以及加密过程中的注意事项。 ... [详细]
  • 如何在PHP中安装Xdebug扩展
    本文介绍了如何从PECL下载并编译安装Xdebug扩展,以及如何配置PHP和PHPStorm以启用调试功能。 ... [详细]
  • 1#include2#defineM1000103#defineRGregister4#defineinf0x3f3f3f3f5usingnamespacestd;6boolrev ... [详细]
author-avatar
高正_飞翔之殇_826
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有