HDU 4302 Holedox Eating （线段树模拟）
2024-08-24 13:09:26
题意：一个老鼠在一条长度为L的直线上跑，吃蛋糕，老鼠只能沿直线移动。开始时没有蛋糕，老鼠的初始位置是0.
有两个操作，0 x 代表在位置x添加一个蛋糕； 1 代表老鼠想吃蛋糕。老鼠每次都会选择离自己最近的点，如果两边距离相同，老鼠优先选择与自己当前移动方向相同的点。
求最终移动的总距离。
题解：线段树单点修改+查询区间端点。
设当前位置为pos，每次查询区间[0, pos]的最右端和区间[pos, L]的最左端，比较选择哪个更近。
详细题解见代码注释。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath> #define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1 #define LEFT 0
#define RIGHT 1 using std::min;
using std::max;
using std::abs; const int MAXN = ;
const int INF = << ; int tr[MAXN << ]; //标记哪个点有蛋糕
int left[MAXN << ]; //标记区间[l, r]内有蛋糕的最左端点
int right[MAXN << ]; //标记区间[l, r]内有蛋糕的最右端点
int N, S;
int findL, findR; //标记查找到的任意区间[l, r]中有蛋糕的最左端和最右端 void PushUp( int rt )
{
int lc = rt << ;
int rc = rt << | ;
left[rt] = min( left[lc], left[rc] );
right[rt] = max( right[lc], right[rc] );
return;
} void build( int l, int r, int rt ) //建树
{
tr[rt] = ; //每个点初始蛋糕数目为0
left[rt] = INF;
right[rt] = -INF;
if ( l == r ) return;
int m = ( l + r ) >> ;
build( lson );
build( rson );
return;
} void Update( int pos, int v, int l, int r, int rt ) //更新
{
if ( l == pos && r == pos )
{
tr[rt] += v; //更新该点的蛋糕数目
if ( tr[rt] == ) //如果这一点没有蛋糕了
{
left[rt] = INF;
right[rt] = -INF;
}
else //如果这一点有蛋糕
{
left[rt] = l;
right[rt] = l;
}
return;
} int m = ( l + r ) >> ;
if ( pos <= m ) Update( pos, v, lson );
else Update( pos, v, rson );
PushUp( rt );
return;
} void Query( int L, int R, int l, int r, int rt ) //查询
{
if ( L <= l && r <= R )
{
findL = min( left[rt], findL );
findR = max( right[rt], findR );
return;
}
int m = ( l + r ) >> ;
if ( L <= m ) Query( L, R, lson );
if ( R > m ) Query( L, R, rson );
return;
} int main()
{
int T, cas = ;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%d%d", &N, &S );
++N; //原题目中pipe长度为L,编号为0-L，实际上是有(L+1)个点，
//之前没注意，RE了一次，在这里我把每个点编号为1-(L+1) int curPos = ; //当前位置
int curDirection = RIGHT; //当前方向
int sum = ; //移动总路程 build( , N, ); //建树 while ( S-- )
{
//printf("**************curPos=%d curDir=%d\n", curPos, curDirection );
int op, pos;
scanf( "%d", &op );
if ( op == )
{
scanf( "%d", &pos );
Update( pos+, , , N, );
}
else
{
bool find = false;
int findpos; if ( curDirection == LEFT ) //如果当前方向向左
{
int LL, RR;
findL = INF;
findR = -INF;
Query( , curPos, , N, ), LL = findR; //向左走，找离当前点最近的右端点
findL = INF;
findR = -INF;
Query( curPos, N, , N, ), RR = findL; //向右走，找离当前点最近的左端点 if ( LL == -INF && RR == INF ) //两边都没有蛋糕
{
find = false;
}
else if ( LL == -INF && RR != INF ) //只有右边有蛋糕
{
find = true;
findpos = RR;
curDirection = RIGHT;
}
else if ( LL != -INF && RR == INF ) //只有左边有蛋糕
{
find = true;
findpos = LL;
curDirection = LEFT;
}
else //两边都有蛋糕
{
find = true;
if ( curPos - LL <= RR - curPos ) //注意等号，两边距离相等时优先选择左边
{
findpos = LL;
curDirection = LEFT;
}
else
{
findpos = RR;
curDirection = RIGHT;
}
} //printf("LEFT: ");
}
else
{
int LL, RR;
findL = INF;
findR = -INF;
Query( curPos, N, , N, ), RR = findL;
findL = INF;
findR = -INF;
Query( , curPos, , N, ), LL = findR; if ( LL == -INF && RR == INF )
{
find = false;
}
else if ( LL == -INF && RR != INF )
{
find = true;
findpos = RR;
curDirection = RIGHT;
}
else if ( LL != -INF && RR == INF )
{
find = true;
findpos = LL;
curDirection = LEFT;
}
else
{
find = true;
if ( curPos - LL < RR - curPos ) //注意没有等号，两边距离相等时优先选择右边
{
findpos = LL;
curDirection = LEFT;
}
else
{
findpos = RR;
curDirection = RIGHT;
}
} //printf("RIGHT: ");
}
//printf( "findL=%d findR=%d\n", findL, findR ); //printf( "findpos = %d\n", findpos );
if ( find )
{
sum += abs( findpos - curPos );
curPos = findpos;
Update( findpos, -, , N, );
}
}
} printf( "Case %d: %d\n", ++cas, sum );
}
return ;
}
最新文章
- mobile touch事件
- Cinemagraph
- iframe获取父、子窗口的方法
- VisualSVN Server以及TortoiseSVN客户端的配置和使用方法
- webdriver(python)学习笔记五——层级定位
- [Windows Azure] Querying Tables and Entities
- jQuery的扩展
- 无法向Windows服务器复制粘贴文件
- 十分钟搞定 pandas
- .Net Core/Framework之Nginx反向代理后获取客户端IP等数据探索
- Mysql常规优化
- 初识SolrJ开发, schema.xml的配置与服务初始化.
- GDAL VS2010 win7(64位)安装、使用说明（图文解析）
- 洛谷 P4593 [TJOI2018]教科书般的亵渎
- poj 3667 线段树
- OneThink友情链接插件使用！
- 一个好工具-everything-可以找到浏览器的所有缓存
- Windows下搭建JSP开发环境
- 【C】switch-case里面，加或不加break的区别
- python练习题4-判断日期是一年的第几天