扫描游戏
蓝桥杯每日一题 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;
}
思考
写了一天了，真的不容易，但是想想线段树这个思想真的是不错的，得多回顾回顾，那么这道题就是你必须具备比较好的代码能力，还有思维扩展能力，加油。
备注
想要一起备赛的同学可以在评论区留言！！！