热门标签 | 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 线段树扫描线


推荐阅读
  • 本文介绍了UUID(通用唯一标识符)的概念及其在JavaScript中生成Java兼容UUID的代码实现与优化技巧。UUID是一个128位的唯一标识符,广泛应用于分布式系统中以确保唯一性。文章详细探讨了如何利用JavaScript生成符合Java标准的UUID,并提供了多种优化方法,以提高生成效率和兼容性。 ... [详细]
  • 尽管我们尽最大努力,任何软件开发过程中都难免会出现缺陷。为了更有效地提升对支持部门的协助与支撑,本文探讨了多种策略和最佳实践,旨在通过改进沟通、增强培训和支持流程来减少这些缺陷的影响,并提高整体服务质量和客户满意度。 ... [详细]
  • 题目《BZOJ2654: Tree》的时间限制为30秒,内存限制为512MB。该问题通过结合二分查找和Kruskal算法,提供了一种高效的优化解决方案。具体而言,利用二分查找缩小解的范围,再通过Kruskal算法构建最小生成树,从而在复杂度上实现了显著的优化。此方法不仅提高了算法的效率,还确保了在大规模数据集上的稳定性能。 ... [详细]
  • 在PHP中如何正确调用JavaScript变量及定义PHP变量的方法详解 ... [详细]
  • 本文探讨了使用JavaScript在不同页面间传递参数的技术方法。具体而言,从a.html页面跳转至b.html时,如何携带参数并使b.html替代当前页面显示,而非新开窗口。文中详细介绍了实现这一功能的代码及注释,帮助开发者更好地理解和应用该技术。 ... [详细]
  • 数字图书馆近期展出了一批精选的Linux经典著作,这些书籍虽然部分较为陈旧,但依然具有重要的参考价值。如需转载相关内容,请务必注明来源:小文论坛(http://www.xiaowenbbs.com)。 ... [详细]
  • WebStorm 是一款强大的集成开发环境,支持多种现代 Web 开发技术,包括 Node.js、CoffeeScript、TypeScript、Dart、Jade、Sass、LESS 和 Stylus。它为开发者提供了丰富的功能和工具,帮助高效构建和调试复杂的 Node.js 应用程序。 ... [详细]
  • 本文总结了JavaScript的核心知识点和实用技巧,涵盖了变量声明、DOM操作、事件处理等重要方面。例如,通过`event.srcElement`获取触发事件的元素,并使用`alert`显示其HTML结构;利用`innerText`和`innerHTML`属性分别设置和获取文本内容及HTML内容。此外,还介绍了如何在表单中动态生成和操作``元素,以便更好地处理用户输入。这些技巧对于提升前端开发效率和代码质量具有重要意义。 ... [详细]
  • 能够感知你情绪状态的智能机器人即将问世 | 科技前沿观察
    本周科技前沿报道了多项重要进展,包括美国多所高校在机器人技术和自动驾驶领域的最新研究成果,以及硅谷大型企业在智能硬件和深度学习技术上的突破性进展。特别值得一提的是,一款能够感知用户情绪状态的智能机器人即将问世,为未来的人机交互带来了全新的可能性。 ... [详细]
  • 本文回顾了作者初次接触Unicode编码时的经历,并详细探讨了ASCII、ANSI、GB2312、UNICODE以及UTF-8和UTF-16编码的区别和应用场景。通过实例分析,帮助读者更好地理解和使用这些编码。 ... [详细]
  • Python 数据可视化实战指南
    本文详细介绍如何使用 Python 进行数据可视化,涵盖从环境搭建到具体实例的全过程。 ... [详细]
  • php更新数据库字段的函数是,php更新数据库字段的函数是 ... [详细]
  • XAMPP 遇到 404 错误:无法找到请求的对象
    在使用 XAMPP 时遇到 404 错误,表示请求的对象未找到。通过详细分析发现,该问题可能由以下原因引起:1. `httpd-vhosts.conf` 文件中的配置路径错误;2. `public` 目录下缺少 `.htaccess` 文件。建议检查并修正这些配置,以确保服务器能够正确识别和访问所需的文件路径。 ... [详细]
  • 深入解析 OpenSSL 生成 SM2 证书:非对称加密技术与数字证书、数字签名的关联分析
    本文深入探讨了 OpenSSL 在生成 SM2 证书过程中的技术细节,重点分析了非对称加密技术在数字证书和数字签名中的应用。非对称加密通过使用公钥和私钥对数据进行加解密,确保了信息传输的安全性。公钥可以公开分发,用于加密数据或验证签名,而私钥则需严格保密,用于解密数据或生成签名。文章详细介绍了 OpenSSL 如何利用这些原理生成 SM2 证书,并讨论了其在实际应用中的安全性和有效性。 ... [详细]
  • 本文详细探讨了在ASP.NET环境中通过加密数据库连接字符串来提升数据安全性的方法。加密技术不仅能够有效防止敏感信息泄露,还能增强应用程序的整体安全性。文中介绍了多种加密手段及其实施步骤,帮助开发者在日常开发过程中更好地保护数据库连接信息,确保数据传输的安全可靠。 ... [详细]
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社区 版权所有