【splay】BZOJ1208宠物收养所

2024-09-01 11:48
文章标签 宠物 splay 收养 bzoj1208

本文主要是介绍【splay】BZOJ1208宠物收养所,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1208: [HNOI2004]宠物收养所

Time Limit: 10 Sec   Memory Limit: 162 MB
Submit: 3620   Solved: 1364
[ Submit][ Status]

Description

最近,阿Q开了一间宠物收养所。收养所提供两种服务:收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物,阿Q根据领养者的要求通过他自己发明的一个特殊的公式,得出该领养者希望领养的宠物的特点值a(a是一个正整数,a<2^31),而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了,宠物收养所总是会有两种情况发生:被遗弃的宠物过多或者是想要收养宠物的人太多,而宠物太少。 1. 被遗弃的宠物过多时,假若到来一个领养者,这个领养者希望领养的宠物的特点值为a,那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。(任何两只宠物的特点值都不可能是相同的,任何两个领养者的希望领养宠物的特点值也不可能是一样的)如果有两只满足要求的宠物,即存在两只宠物他们的特点值分别为a-b和a+b,那么领养者将会领养特点值为a-b的那只宠物。 2. 收养宠物的人过多,假若到来一只被收养的宠物,那么哪个领养者能够领养它呢?能够领养它的领养者,是那个希望被领养宠物的特点值最接近该宠物特点值的领养者,如果该宠物的特点值为a,存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b,那么特点值为a-b的那个领养者将成功领养该宠物。 一个领养者领养了一个特点值为a的宠物,而它本身希望领养的宠物的特点值为b,那么这个领养者的不满意程度为abs(a-b)。【任务描述】你得到了一年当中,领养者和被收养宠物到来收养所的情况,希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时,收养所里面既没有宠物,也没有领养者。

Input

第一行为一个正整数n,n<=80000,表示一年当中来到收养所的宠物和领养者的总数。接下来的n行,按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数a, b,其中a=0表示宠物,a=1表示领养者,b表示宠物的特点值或是领养者希望领养宠物的特点值。(同一时间呆在收养所中的,要么全是宠物,要么全是领养者,这些宠物和领养者的个数不会超过10000个)

Output

仅有一个正整数,表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。

Sample Input

5
0 2
0 4
1 3
1 2
1 5

Sample Output

3
(abs(3-2) + abs(2-4)=3,最后一个领养者没有宠物可以领养)

HINT

Source

Splay

var n,ans,a,b,i,pre,suc,root,tot,min,typ:longint;t:array[0..100001]of recordl,r,f,v:longint;end;procedure left(aa:longint);
var fa:longint;
beginfa:=t[aa].f;t[aa].f:=t[fa].f;if t[t[fa].f].l=fa then t[t[fa].f].l:=aa;if t[t[fa].f].r=fa then t[t[fa].f].r:=aa;t[fa].f:=aa;t[fa].r:=t[aa].l;t[t[aa].l].f:=fa;t[aa].l:=fa;
end;procedure right(aa:longint);
var fa:longint;
beginfa:=t[aa].f;t[aa].f:=t[fa].f;if t[t[fa].f].l=fa then t[t[fa].f].l:=aa;if t[t[fa].f].r=fa then t[t[fa].f].r:=aa;t[fa].f:=aa;t[fa].l:=t[aa].r;t[t[aa].r].f:=fa;t[aa].r:=fa;
end;procedure splay(now,goal:longint);
var fa:longint;
beginwhile t[now].f<>goal dobeginfa:=t[now].f;if t[fa].f=goal thenbeginif t[fa].l=now then right(now) else left(now);endelseif t[t[fa].f].l=fa thenbeginif t[fa].l=now thenbeginright(fa);right(now);endelsebeginleft(now);right(now);end;endelsebeginif t[fa].r=now thenbeginleft(fa);left(now);endelsebeginright(now);left(now);end;end;end;if goal=0 then root:=now;
end;procedure find(x:longint);
var now:longint;
beginnow:=root;repeatif (t[now].v<=x) then pre:=now;if (t[now].v>=x) then suc:=now;if t[now].v=x then exit;if xuntil now=0;
end;procedure insert(v:longint);
var now:longint;
beginnow:=root;while true dobeginif v<=t[now].v thenbeginif t[now].l<>0 then now:=t[now].lelse begininc(tot);t[tot].f:=now;t[tot].v:=v;t[now].l:=tot;splay(tot,0);exit;end;endelseif t[now].r<>0 then now:=t[now].relse begininc(tot);t[tot].f:=now;t[tot].v:=v;t[now].r:=tot;splay(tot,0);exit;end;end;
end;procedure del(x:longint);
var l,r,new,rk:longint;
beginsplay(x,0);l:=t[x].l;r:=t[x].r;if (l=0)and(r<>0) thenbeginroot:=r;t[r].f:=0;exit;end;if (r=0)and(l<>0) thenbeginroot:=l;t[l].f:=0;exit;end;if (r=0)and(l=0) thenbeginroot:=0;t[root].v:=0;t[root].l:=0;t[root].r:=0;typ:=-1;//tot:=0;不知道为什么加了这句就T了= =exit;end;new:=0; rk:=l;while (rk<>0) dobeginnew:=rk; rk:=t[rk].r;end;splay(new,root);root:=t[root].l;t[root].f:=0;t[root].r:=t[x].r;t[t[x].r].f:=root;
end;beginreadln(n);ans:=0;tot:=0;root:=0;typ:=-1;for i:=1 to n dobeginreadln(a,b);if typ=-1 then typ:=a;if a=typ thenbegininsert(b);endelsebeginpre:=0; suc:=0; min:=0;find(b);if suc=0 then min:=pre;if pre=0 then min:=suc;if (pre=0)and(suc=0) thenbegintyp:=a;insert(b);continue;end; //这个地方没注意。。wa了很久if (pre<>0)and(suc<>0) thenif abs(t[pre].v-b)<=abs(t[suc].v-b) then min:=pre else min:=suc;ans:=(ans+abs(t[min].v-b))mod 1000000;del(min);end;end;writeln(ans);
end.


这篇关于【splay】BZOJ1208宠物收养所的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1126851

相关文章

基于SpringBoot的宠物服务系统+uniapp小程序+LW参考示例

系列文章目录 1.基于SSM的洗衣房管理系统+原生微信小程序+LW参考示例 2.基于SpringBoot的宠物摄影网站管理系统+LW参考示例 3.基于SpringBoot+Vue的企业人事管理系统+LW参考示例 4.基于SSM的高校实验室管理系统+LW参考示例 5.基于SpringBoot的二手数码回收系统+原生微信小程序+LW参考示例 6.基于SSM的民宿预订管理系统+LW参考示例 7.基于

除猫毛应该用哪款宠物空气净化器?希喂、安德迈哪款更值得推荐

自从我的朋友也养了猫之后,我和她能讨论的话题就更多了,每天都在分享自家的猫咪今天干了什么可爱的事,一起探讨应该怎么让猫咪胖起来,每天撸都撸不够,好想时时刻刻和猫咪待在一起。 但她说到,本来这种生活挺好的,但是自从养了猫之后,家里的各个角落都开始有猫咪的毛发,每天都得清理,而且还有这个排便时的臭味,家里简直就是无法忍受,导致现在家里的氛围就更差了,她婆婆每天都在担心养了猫之后对家里人造成健

Splay树(区间更新)—— POJ 3468 A Simple Problem with Integers

对应POJ 题目:点击打开链接 A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 72765 Accepted: 22465Case Time Limit: 2000MS Description You have N integers, A1

Splay树(区间添加删除 | 区间翻转)——HDU 3487 Play with Chain

对应HDU题目:点击打开链接 Play with Chain Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4571    Accepted Submission(s): 1859 Problem Descript

SprinBoot+Vue宠物领养救助微信小程序的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue3.6 uniapp代码 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍:CSDN认证博客专家,CSDN平台Java领域

宠物空气净化器真的有用吗?哪款能真的起到吸毛除臭效果

现在养猫养狗已经成为了一个浪潮,甚至有人发了一张对比图:在店门口,偏年老一代的就是抱着小孩,但年轻一辈的就是抱着宠物。虽然说不管是养猫养狗还是养小孩都是自己的选择,但是显而易见的就是现在大街上宠物出现的频率明显变多,对于大部分独居青年而言,养宠物反而是一个精神寄托,甚至成为精神支撑,支撑着这些年轻人在城市里打拼。 对于我而言,之前养猫就是觉得一个人太孤独,回到家后发现家里并没有什么能和我

宠物空气净化器真的有用吗?去浮毛好用的宠物空气净化器推荐

不知不觉我已经养宠五年了,一人两猫作伴的日子充满着幸福,可猫毛的存在偶尔也会让小家出现裂缝。每当换毛季,我的鼻子就率先作出反应,瘙痒加上止不住喷嚏都在反映着不佳的空气质量。这都是因为猫咪疯狂掉毛,浮毛上附着的细菌随着呼吸进入到人体,引起各种反应。 朋友在看到后,推荐我买台宠物空气净化器来改善家中的环境。相信很多人和我一样,对宠物空气净化器了解不是很多,更别提知道它的功能了。为了可以减轻家中猫毛打

除猫毛用哪家宠物空气净化器?希喂、有哈测评推荐

作为一个养宠多年、经验丰富的铲屎官,我和这些小毛球相处的每一天都充满了欢乐。每当傍晚时分,家中的猫咪会慵懒地蜷缩在窗边,有时就会跳跃在各个角落,这份纯真与陪伴,确实让生活的每个角落都洋溢着无可替代的幸福与温馨。然而,正如每枚硬币都有两面,这份甜蜜背后也伴随着一系列日常的小挑战,虽然是个小事,但是也让人头疼不已。 猫毛,这个看似无害却无处不在的东西,几乎成了我日常清洁的头号劲敌。无论是精心

【精选】基于HTML5技术应用于智能宠物寻找与领养系统的设计与实现(全网独一无二,阿龙独创)

博主介绍:     ✌我是阿龙,一名专注于Java技术领域的程序员,全网拥有10W+粉丝。作为CSDN特邀作者、博客专家、新星计划导师,我在计算机毕业设计开发方面积累了丰富的经验。同时,我也是掘金、华为云、阿里云、InfoQ等平台的优质作者。通过长期分享和实战指导,我致力于帮助更多学生完成毕业项目和技术提升。 技术范围:     我熟悉的技术领域涵盖SpringBoot、Vue、SSM、HLMT

springboot宠物智慧医院-计算机毕业设计源码99362

目录 摘要 1 绪论 1.1 选题背景与意义 1.2国内外研究现状 1.3微信开发者工具 1.4小程序框架以及目录结构介绍 1.5论文结构与章节安排 2系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1系统开发流程 2.2.2 用户登录流程 2.2.3 系统操作流程 2.2.4 添加信息流程 2.2.5 修改信息流程 2.2.6 删除信息流程 2.3