1.2 提高组
1.2.1 蚯蚓
【例题讲解】蚯蚓(earthworm)NOIP 2016
本题中,我们将用符号c表示对c向下取整,例如:3.0=3.1=3.9=3。
“蛐蛐国”最近蚯蚓成灾了!“蛐蛐国王”只好去请“神刀手”来帮他们消灭蚯蚓。
蛐蛐国里现在共有n(n为正整数)只蚯蚓。每只蚯蚓都有一定的长度,我们设第i只蚯蚓的长度为ai ( i=1,2,…,n),并保证所有蚯蚓的长度都是非负整数(可能存在长度为0的蚯蚓)。
每一秒,神刀手都会在所有的蚯蚓中准确地找到最长的那一只(如有多只则任选一只),然后将其切成两半。神刀手切开蚯蚓的位置由常数p(p是满足0<p<1的有理数)决定,设这只蚯蚓长度为x,神刀手会将其切成两只长度分别为 px 和x-px 的蚯蚓。特殊地,如果这两个数的其中一个为0,则这只长度为0的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加q(q是一个非负整数)。
蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助一位有着“洪荒之力”的神秘人物,但是救兵还需要m(m为非负整数)秒才能到来……蛐蛐国王希望知道:
m秒内,每一秒被切断的蚯蚓被切断前的长度(有m个数);
m秒后,所有蚯蚓的长度(有n+m个数)。
【输入格式】
第1行包含6个整数n,m,q,u,v,t,其中:n、m、q的意义见例题讲解;u、v、t均为正整数;你需要自己计算p=u/v(保证0<u<v)的值;t是输出参数,其含义将会在输出格式中解释。
第2行包含n个非负整数,为 a1,a2,…,an,即初始时n只蚯蚓的长度。
同一行中相邻的两个数之间用一个空格分隔。
保证1≤n≤105,0≤m≤7×106,0<u<v≤109,0≤q≤200,1≤t≤71,0≤ai≤108。
【输出格式】
第1行输出m/t个整数,按时间顺序,依次输出第t秒、第2t秒、第3t秒……被切断蚯蚓(在被切断前)的长度。
第2行输出(n+m)/t个整数,输出m秒后所有蚯蚓的长度:需要按从大到小的顺序,依次输出第t秒、第2t秒、第3t秒……时蚯蚓的长度。
同一行中相邻的两个数之间用一个空格分隔。即使某一行没有任何数需要输出,也应输出一行空行。
请阅读输入样例来更好地理解这个格式。
【输入样例1】
3 7 1 1 3 1
3 3 2
【输出样例1】
3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2
【样例1说明】
在神刀手到来前:3只蚯蚓的长度为3、3、2,p为1/3。
1秒后:一只长度为3的蚯蚓被切成了两只长度分别为1和2的蚯蚓,其余蚯蚓的长度增加了1。最终4只蚯蚓的长度分别为(1、2)、4、3。括号表示这个位置刚刚有一只蚯蚓被切断。
2秒后:一只长度为4的蚯蚓被切成了1和3。5只蚯蚓的长度分别为2,3,(1、3),4。
3秒后:一只长度为4的蚯蚓被切断。6只蚯蚓的长度分别为3,4,2,4,(1、3)。
4秒后:一只长度为4的蚯蚓被切断。7只蚯蚓的长度分别为4,(1、3),3,5,2,4。
5秒后:一只长度为5的蚯蚓被切断。8只蚯蚓的长度分别为5,2,4,4,(1、4),3,5。
6秒后:一只长度为5的蚯蚓被切断。9只蚯蚓的长度分别为(1、4), 3,5,5,2,5,4,6。
7秒后:一只长度为6的蚯蚓被切断。10只蚯蚓的长度分别为2,5,4,6,6,3,6,5,(2、4)。
所以,7秒内被切断的蚯蚓的长度依次为3,4, 4,4,5,5,6。7秒后,所有蚯蚓长度从大到小排序为6,6,6,5,5,4,4,3,2,2。
【输入样例2】
3 7 1 1 3 2
3 3 2
【输出样例2】
4 4 5
6 5 4 3 2
【样例 2说明】
这个样例中只有t=2与上个数据不同。只需在每行都改为每两个数输出一个数即可。
虽然第1行最后有一个6没有被输出,但是第2行仍然要重新从第2个数再开始输出。
【输入样例3】
3 7 1 1 3 9
3 3 2
【输出样例3】
2
【样例3说明】
这个数据中只有t=9与上个数据不同。注意:第1行没有数要输出,但也要输出一行空行。
【算法分析】
一种简单的方法是将每一只蚯蚓的长度都放入一个优先队列(大根堆)中,每次从堆顶(队首)取出最长的那只蚯蚓切成两段,再将新产生的两只蚯蚓直接放回优先队列即可,因为优先队列的特性之一是自动排序。神刀手操作m次后,逐个输出队首(堆顶)的数即可。这种使用STL中的优先队列存储所有的蚯蚓,模拟神刀手的操作过程可以处理大部分测试数据。
要想通过全部测试数据,需要对操作过程进行优化,即神刀手每次操作后,其余蚯蚓的增长没有必要实时更新,可以定义一个变量sum统计其余蚯蚓的总增长量。操作过程中,如果切断的蚯蚓入队,给它减去sum减去q的长度;如果队首的蚯蚓出队,给它加上sum的长度后再处理即可。
参考代码如下。
1 //蚯蚓 —— 使用优先队列模拟可处理大部分数据
2 #include <bits/stdc++.h>
3 using namespace std;
4
5 int main()
6 {
7 priority_queue<int> earthworm; //优先队列默认由大到小排列蚯蚓长度
8 int n,m,t,q,u,v,sum=0; //sum用于保存累计增加的q值
9 cin>>n>>m>>q>>u>>v>>t;
10 double p=double(u)/v;
11 for(int i=0,temp; i<n; ++i)
12 {
13 cin>>temp;
14 earthworm.push(temp); //入队列
15 }
16 for(int i=1; i<=m; i++)
17 {
18 int Big=earthworm.top()+sum; //队首为最大值,出队时还原回真实值
19 earthworm.pop(); //删除队首的蚯蚓
20 if(!(i%t)) //输出第i*t秒切的蚯蚓
21 cout<<Big<<" ";
22 int cut=floor(p*double(Big)); //用floor函数,以防因编译器不同而出现误差
23 earthworm.push(cut-sum-q); //被切割的蚯蚓无须加q,所以先减去
24 earthworm.push(Big-cut-sum-q);
25 sum+=q; //累计增长量
26 }
27 cout<<'\n';
28 for(int i=1; i<=n+m; ++i)
29 {
30 if(!(i%t))
31 cout<<earthworm.top()+sum<<' ';
32 earthworm.pop(); //逐个删除队首的蚯蚓
33 }
34 cout<<'\n';
35 return 0;
36 }
因为每一次操作都要找出最大的一个数,如果用排序的方法会超时,所以考虑采用3个由大到小排列的队列来完成(使用STL里的优先队列会超时,需要自己编写代码)。第1个队列p[0]保存的是已经由大到小排好序的n只蚯蚓的长度,p[2]、p[3]分别保存每一次切割后的前半段和后半段长度,每次取3个队列中队首最大的元素进行切割后存入p[2]和p[3]中,请思考p[2]、p[3]需要由大到小排序吗?
试根据以上分析,完成满分代码(指完成的代码可通过全部测试数据)。