首页 > [NOIP2016]蚯蚓

Kur1su

发表于 2020-08-22 16:29:37

Description Solution 难点在于题目太长了，输出也很麻烦。需要注意到 , 用优先队列每次找最大值显然是不可行的，需要寻找的做法。对于一个数字，如果按照题目将它分成和 , 如果 , 那么满足和基于以上性质，可以开三个队列，分别有：原来的蚯蚓分割出来的蚯蚓展开全文

活泼泼

发表于 2021-04-16 21:18:07

如果x1>x2，那么floor(px1)>floor(px2)，且x1-floor(px1)>x2-floor(px2)因此，可以把原来的蚯蚓、切开后长的蚯蚓、切开后短的蚯蚓分别放入三个队列，每次只需取三个队列中front的最大数，就是当前蚯蚓的最大长度另外为了统一，规定放进队列时展开全文

在刷题的单身狗很开心

发表于 2023-09-11 21:21:36

使用优先队列会超时，因为优先队列的内部实现是小根堆或大根堆。并不是O(N)的时间复杂度。在本题当中可以使用三个队列，一个原始序列排序好的队列，一个切完后左边蚯蚓的队列，一个切完后右边蚯蚓的队列。这样只需要每次比较队首的蚯蚓长度就可以得到刽子手需要去砍的蚯蚓。然后本题的输出比较麻烦，需展开全文

hnust_yangyanjun

发表于 2020-09-01 11:46:19

题意：有n条蚯蚓，在m秒内每一秒选择最长的一条蚯蚓分成二份，其余蚯蚓增长q长度，然后按要求输出。思路：用二个队列进行模拟，维护二个队列的单调性，一个队列加入长的，另一个队列加入短的，这样二个队列就是单调的，队列中保持0时刻的长度。代码：展开全文

白菜茄子

发表于 2020-03-16 00:01:36

网址：https://ac.nowcoder.com/acm/contest/3888/F 题目描述本题中，我们将用符⌊c⌋ 表示对 c 向下取整，例如：⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。蛐蛐国里展开全文

ExcaIibur

发表于 2020-08-22 21:03:53

题目链接题意：在m秒中有n只蚯蚓不断被分割，即每秒中长度最长的一只会被分割成两段，其余蚯蚓长度会增加q。求出每秒所分割的蚯蚓长度和最后各蚯蚓长度，按照格式要求输出。题解：暴力维护肯定会T，可以按照相对的思想，只对分割的蚯蚓操作，即分割蚯蚓长度少增加了q，大小关系不变，真正的长度等于队列展开全文

savage

发表于 2019-09-02 12:34:18

题目描述本题中，我们将用符号表示对 c 向下取整，例如：。蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。蛐蛐国里现在共有 n 只蚯展开全文

henry_y

发表于 2019-09-02 21:56:44

很有意思的一道题。对于每秒的增长，因为是个定值，所以显然可以打标记处理，记录每只蚯蚓被切断的时间，那么这只增长量就是，可以利用一个堆来维护当前的最大长度，那么可以做到，这样子已经可以通过5分了（卡常卡的好一点就85）。这题最有意思的地方就是按题目规则切出来的蚯蚓都是有单调性的。对于当前切出来的两只蚯展开全文

昵称很长很长真是太好了

发表于 2020-08-23 22:20:48

题解：这个题真的是停麻烦的，一不看题就要忘记干什么。。。首先这些个蚯蚓的长度是不断增加的（所有蚯蚓都在增加），所以在处理的过程中，先把增加的长度省去，只处理未增加长度。如果用优先队列复杂度就是O（m*logn）这样的时间复杂度必然超时。看了看网上的题解，哦豁然开朗。用三个队列即可实现证明如下：如果展开全文

一只羊蝎子

发表于 2021-02-16 21:25:11

题意表示对向下取整第0秒，你有只蚯蚓，第只蚯蚓的长度为（长度均为非负整数，可以为0）。每过一秒找出最长的蚯蚓切成两条长度为和的蚯蚓，为0到1之间的有理数，同时其余的所有蚯蚓长度增加（非负整常数）。问秒内每一秒被切断的蚯蚓被切断前的长度和秒后所有蚯蚓的长度思路每秒都要找最长的蚯蚓切成两条，因为新展开全文

查看本题

查看本题讨论

等你来战

查看全部

牛客练习赛127

报名截止时间：2024-07-05 21:30
牛客周赛 Round 50

报名截止时间：2024-07-07 21:00
牛客小白月赛98

报名截止时间：2024-07-12 21:00
2024牛客暑期多校训练营1

报名截止时间：2024-07-16 17:00
2024牛客暑期多校训练营2

报名截止时间：2024-07-18 17:00

相关比赛

等你来战