wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
LYOJ 213「雅礼集训 2017 Day10」决斗
? solution ?
? 贪心 ?
2017-03-23 19:51:38
457
0
0
wuvin
? solution ?
? 贪心 ?
##题目描述 Mirko 是侏儒国的国王,Slavko 是精灵国的国王。最近,侏儒国和精灵国进行了一场战争。Slavko 率领着 $N$ 个最强壮的精灵(编号从 $1$ 到 $N$)进攻侏儒国,而侏儒国的城堡也由 $N$ 个侏儒(按顺时针方向从 $1$ 到 $N$ 编号并形成环形)进行防守。 Mirko 为每一个精灵分配了一个侏儒对手 $A_i$,表示编号为 $i$的精灵要与编号为$A_i$的侏儒进行对决。然而,不久后他就发现,这个方案不能保证每一个侏儒都与唯一一个精灵进行对决。 经过协商,Mirko 和 Slavko 最终定下了如下规则: Slavko 会按他安排的顺序依次派遣他的精灵进入城堡。一个精灵进入城堡时,上一个进入的精灵必须已经找到了就座的位置并坐下。 编号为 $k$ 的精灵进入城堡时,会首先靠近编号为$A_k$的侏儒。如果该侏儒旁边的位置没有精灵就座,则该精灵在该位置就座。否则,他将沿着顺时针方向走到下一个侏儒旁的位置,直到他找到一个空位为止。 最终, $N$ 个精灵和侏儒将一一配对,并进行一对一的对决,其中更有力量的一个将会胜出。 Slavko 已经为这场战斗做了充分的准备,他已经知道了每一个精灵和侏儒的力量大小。现在他想直到,合理安排精灵进入城堡的顺序后,他的精灵们最多能赢得多少场对决。 ##输入格式 第一行一个整数 $N$。 第二行 $N$ 个整数 $A_i$; 第三行 $N$ 个整数,其中第 $i$ 个整数表示第 $i$ 个侏儒的力量值; 第三行 $N$ 个整数,其中第 $i$ 个整数表示第 $i$ 个精灵的力量值。 ##输出格式 输出一行一个整数,表示精灵们最多赢得多少场对决。 ##样例 ###样例输入 1 3 2 3 3 4 1 10 2 7 3 ###样例输出 1 2 ###样例输入 2 4 3 1 3 3 5 8 7 10 4 1 2 6 ###样例输出 2 1 ###样例输入 3 3 1 2 3 8 4 3 9 2 6 ###样例输出 3 2 ##数据范围与提示 对于 $40\%$的数据, $A_i = 1$; 对于 $100\%$ 的数据, $1 \leq N \leq 5 \times 10 ^ 5$。 保证输入的力量值互不相同,且在 $[1, 10 ^ 9]$ 的范围内。 ##题解 <br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br> 贪心 ####结论1: 如果精灵$i$从位置$A_i$,最终走到$C_i$。那么他可以替换$A_i$到$C_i$上已经坐下了的精灵。 替换方法是在入座序列中将他们交换就可以了。 然后我们就可选择一个科学的开头开始贪心,开头$x$需要满足无论怎么安排都没有精灵因为找位置从$x-1$走到$x$。 这个开头就,每个位置赋值成指向这个位置的精灵个数-1,然后做个前缀和找最小值后面一个位置就好了。 然后我们可以一次选择每个位置上座谁,贪心选择力量大于等于当前力量的最小的就好了。然后切换到下一个位置,把所有指向当前位置的精灵都加入备选方案。 这样贪心正确性显然。
上一篇:
LYOJ 215 「雅礼集训 2017 Day10」数列
下一篇:
LYOJ 213 「雅礼集训 2017 Day8」爷
0
赞
457 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
没有帐号? 立即注册