HDU2795Biliboard
发布日期:2021-08-19 11:09:59 浏览次数:1 分类:技术文章

本文共 1962 字,大约阅读时间需要 6 分钟。

  用线段树来表示,每个区间节点存储当期区间剩余的最大长度,每次“贴告示”的时候找到区间中最左的且剩余长度大于告示长度的叶节点,将其剩余长度减去告示长度并更新树。

#include
      
       using namespace std;struct lineNode;typedef lineNode lineTree;struct lineNode{
       
int left, right;
int val;
lineNode(int l=0, int r=0, int val=0) :left(l),
right(r), val(val) {}}nodeArr[800020];void build(int pos, int l, int r, int val){
nodeArr[pos] = lineNode(l, r, val);
if (l != r)
{
build(pos * 2, l, (l + r) / 2, val);
build(pos * 2 + 1, (l + r) / 2 + 1, r, val);
}}void UpdateVal(int node){
int fatherNode = node / 2;
if (fatherNode == 0) { return; }
int lVal = nodeArr[fatherNode * 2].val;
int rVal = nodeArr[fatherNode * 2 + 1].val;
nodeArr[fatherNode].val = lVal > rVal ? lVal : rVal;
UpdateVal(fatherNode);}void UpdateNode(int node, int val){
nodeArr[node].val = val;
UpdateVal(node);}int findMaxValNode(int tree, int val){
if (nodeArr[tree].left == nodeArr[tree].right)
{
UpdateNode(tree, nodeArr[tree].val - val);
return tree;
}
if (val <= nodeArr[2 * tree].val)
{
return findMaxValNode(2 * tree, val);
}
else if (val <= nodeArr[2 * tree + 1].val)
{
return findMaxValNode(2 * tree + 1, val);
}
else
{
return 0;
}}int main(){
int h, w, n;
while (cin>>h>>w>>n)
{
if (h > 200005)h = 200005;
build(1, 1, h, w);
int wi;
for (int i = 0; i < n; ++i)
{
scanf("%d", &wi);
if (nodeArr[1].val < wi)printf("-1\n");
else
{
int tarNode = findMaxValNode(1, wi);
if (tarNode == 0)
{
printf("-1\n");
}
else printf("%d\n", nodeArr[tarNode].left);
}
}
}}
View Code

  另外,如果用指针来表示线段树会MLE。因为线段树是完全二叉树所以用数组来存储是最节约空间的。

转载于:https://www.cnblogs.com/Algorithm-X/p/7528153.html

转载地址:https://blog.csdn.net/weixin_30924087/article/details/96979845 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Linux下对lvm逻辑卷分区大小的调整(针对xfs和ext4不同文件系统)
下一篇:前沿技术

发表评论

最新留言

网站不错 人气很旺了 加油
[***.172.111.71]2022年05月22日 08时56分03秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

moz浏览器html背景音乐自动播放,H5案例---解决H5中背景音乐无法自动播放问题 2019-06-25 13:15:18
三星 android 调试模式设置,三星galaxy s4 usb调试在哪里 s4 usb调试模式设置方法详解... 2019-06-25 13:15:17
打砖块游戏html代码,打砖块游戏的源代码 2019-06-25 13:15:17
android常用控件实验报告,常用控件的编程实验报告 2019-06-25 13:15:17
android后台数据库,Android后台数据接口类型 2019-06-25 13:15:16
Android 友盟的计数功能,Android-集成Umeng统计 2019-06-25 13:15:16
c语言短整型范围越界,[原创]数组越界之入门向 2019-06-25 13:15:15
c语言怎么显示当前星期几,计算任何一天是星期几的C语言源代码. 2019-06-25 13:15:15
c语言内存管理线程,C语言多线程内存管理模块.doc 2019-06-25 13:15:14
开心猫序列C语言,曾婷婷| 2019-06-25 13:15:14
c语言程序中要用到阶乘,C程序使用递归求数字的阶乘 2019-06-25 13:15:13
Linux命令完全指南sysctl,linux的sysctl命令以及相关应用 2021-08-28
linux dev core,c# – 在Linux上运行.NET Core – 什么都不写 2021-08-28
linux0.11体系结构,linux的系统结构 2021-08-28
linux的python简单调试,Python的学习(二十九)---- linux下python调试 2021-08-28
linux rm rf加文件夹,linux下用rm -rf误删了文件夹后 2021-08-28
linux 做nfs备份服务器,Linux下快速搭建NFS服务 2021-08-28
linux命令及作用,linux常用的50个命令作用 2021-08-28
pppoe linux软件,LINUXPPPOEV6服务器搭建测试(最新整理) 2021-08-28
linux无盘工作站视频教程,Linux无盘工作站架设案例基础教程 2021-08-28