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