【蓝桥杯每日一题】扫描游戏——线段树

devtools/2024/12/23 9:20:18/

扫描游戏

蓝桥杯每日一题 2024-12-13 扫描游戏 线段树 模拟

题目大意

有一根围绕原点 O 顺时针旋转的棒 O A OA OA ,初始时指向正上方 (Y 轴正向)。 在平面中有若干物件, 第 i 个物件的坐标为 ( x i , y i ) (x_i,y_i) (xi,yi), 价值为 z i z_i zi 。当棒扫到某个 物件时, 棒的长度会瞬间增长 z i z_i zi, 且物件瞬间消失(棒的顶端恰好碰到物件也 视为扫到), 如果此时增长完的棒又额外碰到了其他物件, 也按上述方式消去 (它和上述那个点视为同时消失)。

如果将物件按照消失的时间排序, 则每个物件有一个排名, 同时消失的物 件排名相同, 请输出每个物件的排名, 如果物件永远不会消失则输出 −1 。

解题思路

本题的思路来自于一位大佬:大佬的博客 先膜拜一下,orz

下面我根据大佬的思路自己再理一遍,本题可分为基础版和完美版:

基础版(70%):

​ 根据题目描述来模拟每次扫描到的值,但是由于时间限制会超时!那么在学习之前要了解到的知识:atan2函数的用法及含义、结构体的构造函数的使用、重载运算符
在本题中,扫描的顺序可以通过极角来排序,如果极角相等的话,按照到原点的长度从小到大排序。然后找出那个极角最大的那个点(也就是如果长度足够一定扫到的第一个点),这是用于后续判断是否在同一个极角大小上的一个预处理。然后通过无限循环(当然是循环到扫不到点就结束了),先找到能够扫描到的第一个点(即将要优化的点),然后判断极角是跟之前一样还是跟之前的不同来更新排名。
最后在每次循环中都会更新当前节点值,木棍长度、将扫描过的做标记、本次的排名。 然后输出结果即可。

完美版(100%):

​ 这个要学到的知识就是:基本线段树的用法
线段树的优化就是上面提到的优化点;使用的操作就是线段树构造,区间修改,单点查询,更新pushUp操作。还有就是在查找的时候分为两边:1、[idx,n] 2、[1,idx];依次找这两个区间的最小值。这个线段数的用法是通过每一个点到原点的距离所构成的序列,然后更新每个区间中的最小值。

70分
#include <bits/stdc++.h>using namespace std;const int N = 2e5+10;
const double eps = 1e-10;
struct Node {double x,y,z,d;double ata;int idx;Node(){}Node(double xx,double yy,double zz,double i) {x = xx;y = yy;z = zz;d = sqrt(x * x + y * y);ata = atan2(y,x);idx = i;}
}; double equals(double a, double b) {return abs(a-b) < eps;
}// 重载的中atan2为第一优先级从大到小,然后再从小到大排到原点距离 
bool operator < (const Node &a,const Node &b) {if(equals(a.ata,b.ata)) {return a.d < b.d;}return a.ata > b.ata;
} int n,rnk,idx,lastRank,lastIdx;
double L,x,y,z;
int ansRank[N];
Node node[N];int findNext(int idx,double L) {// 通过圆圈循环找到第一个可以扫描到的下标 for(int i = 0;i < n;i++) {int ii = (i + idx) % n;if(node[ii].d <= L) {return ii;}}return INT_MAX;
}int main() {cin>>n>>L;for(int i = 0;i < n;i++) {cin>>x>>y>>z;node[i] = Node(x,y,z,i);    // 通过有参构造计算出到原点的距离和atan2的值 ansRank[i] = -1;    // 初始化当前节点的排名 }// 根据重载运算符 < 来进行排序 sort(node,node + n);// 查找到第一个根据角度排可以找到的点,不考虑是否能扫描到 Node tmp = Node(0,1,0,0); // 这是定义了一个极角较大的情况 idx = 0; for(int i = 0;i < n;i++) {// 由于重载了 < 运算符 // 这里就是找第一个比初始化极角小的值 if(!(node[i] < tmp)) {idx = i;break;}} lastRank = 1; while(true) {++ rnk;    // 记录排名 int idxTmp = findNext(idx,L);     // 未找到立即跳出循环 if(idxTmp == INT_MAX) {break;}// 判断是否与之前找到极角相同 if(!equals(node[idx].ata,node[idxTmp].ata)) {// 不同,更新成新的排名 ansRank[node[idxTmp].idx] = rnk;} else {// 上面那个找到第一个极角 的作用就在这里,以后就会根据请款更新 // 相同,更新成上一个排名 ansRank[node[idxTmp].idx] = lastRank;}// 下次要紧接着这次找到的下标再循环 idx = idxTmp; // 更新木棍的长度 L += node[idx].z;// 把遍历过的点到原点的距离更新成无限大     node[idx].d = DBL_MAX;// 更新上一次的找到的极角 lastRank = ansRank[node[idx].idx];}for(int i = 0;i < n;i++) {cout<<ansRank[i]<<" ";}cout<<endl;return 0;
}
Accepted
#include <bits/stdc++.h>using namespace std;const int N = 2e5+10;
const double eps = 1e-10;
int n,rnk,lastRank,idx,lastIdx;
int ansRank[N];
double L;struct Node {// 节点基本信息// 坐标 权值 到原点距离 极角 编号 double x,y,z;double d,ata;int idx;Node(){}Node(double xx,double yy,double zz,int i) {x = xx;y = yy;z = zz;d = sqrt(xx*xx + yy*yy);idx = i;ata = atan2(yy,xx);} 
}node[N];bool equals(double a,double b) {return abs(a-b) < eps;
}bool operator < (const Node &a,const Node &b) {if(equals(a.ata,b.ata)) {return a.d < b.d;}return a.ata > b.ata;
}// 线段树相关操作 
struct SegmentTree {double mn[N << 2];    // 开到正常的四倍void pushUp(int u) {mn[u] = min(mn[u<<1],mn[u<<1|1]);}void build (int u,int l,int r,Node *node) {if (l == r) {mn[u] = node[l].d;return ;}int mid = l + r >> 1;build(u<<1,l,mid,node);build(u<<1|1,mid+1,r,node);pushUp(u);}void update(int u,int l,int r,int idx,double x) {if(l == r) {mn[u] = x;return ;}int m = l + r >> 1;if(idx <= m) {update(u<<1,l,m,idx,x);} else {update(u<<1|1,m+1,r,idx,x);}pushUp(u);}// [l,r] 是原始区间,而[L,R]是要查的区间 int query(int u ,int l,int r,int L,int R,double x) {// 如果原始区间被包含 if(L <= l && r <= R) {// 判断是否存在可以扫到的点 if(mn[u] > x) {return INT_MAX;}// 如果找到了叶子结点返回即可 if(l == r) {return l;}}// 开始区分区间 int m = (l + r) >> 1;int ret = INT_MAX;if(L <= m) {ret = query(u<<1,l,m,L,R,x);}// 如果找到,即返回 if(ret != INT_MAX) {return ret;}// 另一区间 if(m < R) {ret = query(u<<1|1,m+1,r,L,R,x);}return ret;}};
SegmentTree t;void update() {// 更新节点值 以及 木棍的长度 L += node[idx].z;// 更新线段树 更新距离为最大值 t.update(1,1,n,idx,DBL_MAX);// 判断更新极角大小 if(!equals(node[lastIdx].ata,node[idx].ata)) {ansRank[node[idx].idx] = rnk;} else {ansRank[node[idx].idx] = lastRank;}// 更新之前的排名和索引 lastRank = ansRank[node[idx].idx];lastIdx = idx;
}int main() {cin>>n>>L;for(int i = 1;i <= n;i++) {int x,y,z;cin>>x>>y>>z;node[i] = Node(x,y,z,i);ansRank[i] = -1;}sort(node+1,node+n+1);// 构建线段树 t.build(1,1,n,node); // 通过二分查找到第一个根据角度所找到的点 idx = lower_bound(node+1,node+1+n,Node(0,1,0,0)) - node;// 处理一下超出范围的点 if(idx == n+1) {idx = 1;}// 跟新上一个点的索引及排名 lastIdx = idx;lastRank = 1;while(true) {++rnk;     // 更新排名int idxTmp = idx;// 单点查询区间[idx,n]的最小值 idx = t.query(1,1,n,idx,n,L);if(idx!= INT_MAX) {update();continue;}idx = idxTmp;idx = t.query(1,1,n,1,idx,L);if(idx != INT_MAX) {update();continue;}break;}for(int i = 1;i <=  n;i++) {cout<<ansRank[i]<<" ";}cout<<endl;return 0;
}
思考

写了一天了,真的不容易,但是想想线段树这个思想真的是不错的,得多回顾回顾,那么这道题就是你必须具备比较好的代码能力,还有思维扩展能力,加油。

备注

想要一起备赛的同学可以在评论区留言!!!


http://www.ppmy.cn/devtools/144648.html

相关文章

uni-app开发商品分类页面实现

目录 一:功能概述 二:功能实现 一:功能概述 这里商品分类按照常规的分类页面样式设计,左侧为一级分类,右侧为二级分类。在左侧切换不同的一级分类可以修改右侧的二级分类数据。右侧的展现方式是最上面显示对应的一级分类logo图片,下面展示二级分类的logo和名称。 二:…

MFC/C++学习系列之简单记录13

MFC/C学习系列之简单记录13 前言memsetList Control代码注意 总结 前言 今天记录一下memset和List control 的使用吧&#xff01; memset memset通常在初始化变量或清空内存区域的时候使用&#xff0c;可以对变量设定特定的值。 使用&#xff1a; 头文件&#xff1a; C&#…

获取显示器(主/副屏)友好名称(FriendlyName)

在开发涉及多显示器的应用程序时&#xff0c;获取显示器的友好名称&#xff08;Friendly Name&#xff09;是一个常见需求。本文将深入探讨GetMonitorFriendlyName 方法&#xff0c;了解其实现细节和工作原理。 方法签名 public static string GetMonitorFriendlyName(bool i…

Debian 10上使用UFW设置防火墙

介绍 UFW或Uncomplicated Firewall是iptables一个接口&#xff0c;旨在简化配置防火墙的过程。 虽然iptables是一个可靠而灵活的工具&#xff0c;但初学者很难学会如何使用它来正确配置防火墙。 如果您希望开始保护网络并且不确定使用哪种工具&#xff0c;UFW可能是您的正确选…

构建全面的生产监控体系:从基础设施到业务服务

在现代 IT 系统中&#xff0c;监控体系是确保高可用性、高性能和稳定性的核心工具。一个完善的监控体系能够及时发现系统问题、分析问题根源并快速采取应对措施&#xff0c;避免故障进一步扩散。本文将从基础设施层、中间件层、容器与编排层、应用与服务层逐步展开&#xff0c;…

每天40分玩转Django:实操在线商城

实操在线商城 一、今日学习内容概述 模块重要程度主要内容商品模型⭐⭐⭐⭐⭐商品信息、分类管理购物车系统⭐⭐⭐⭐⭐购物车功能实现订单系统⭐⭐⭐⭐⭐订单处理、支付集成用户中心⭐⭐⭐⭐订单管理、个人信息 二、模型设计 # models.py from django.db import models fro…

CSS3 实现火焰-小火苗效果

创建 CSS3 火焰效果可以通过组合 CSS 动画、伪元素 和 渐变 来实现。以下是一个简单的实现步骤&#xff0c;展示如何制作动态火焰效果 1. HTML 结构 我们只需要一个简单的 div 容器&#xff1a; <div class"fire"></div>2. CSS 实现 基础样式 使用 …

vi或vim进行替换

vi 中去搜索特定字符串cdc_,替换为aaa_ 在 vi 或 vim 编辑器中&#xff0c;你可以使用以下命令来查找特定的字符串 cdc_ 并将其替换为 aaa_&#xff1a; 打开文件&#xff1a; vi filename 搜索 /cdc_ 按n 是搜索下一个 进入替换模式&#xff1a; :%s/cdc_/aaa_/g 解释&#…