信息学竞赛宝典:基础算法
上QQ阅读APP看书,第一时间看更新

1.2 提高组 

1.2.1 蚯蚓

【例题讲解】蚯蚓(earthworm)NOIP 2016 

本题中,我们将用符号c表示对c向下取整,例如:3.0=3.1=3.9=3。

“蛐蛐国”最近蚯蚓成灾了!“蛐蛐国王”只好去请“神刀手”来帮他们消灭蚯蚓。

蛐蛐国里现在共有nn为正整数)只蚯蚓。每只蚯蚓都有一定的长度,我们设第i只蚯蚓的长度为ai ( i=1,2,…,n),并保证所有蚯蚓的长度都是非负整数(可能存在长度为0的蚯蚓)。

每一秒,神刀手都会在所有的蚯蚓中准确地找到最长的那一只(如有多只则任选一只),然后将其切成两半。神刀手切开蚯蚓的位置由常数pp是满足0p1的有理数)决定,设这只蚯蚓长度为x,神刀手会将其切成两只长度分别为 px 和x-px 的蚯蚓。特殊地,如果这两个数的其中一个为0,则这只长度为0的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加qq是一个非负整数)。 

蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助一位有着“洪荒之力”的神秘人物,但是救兵还需要mm为非负整数)秒才能到来……蛐蛐国王希望知道:

m秒内,每一秒被切断的蚯蚓被切断前的长度(有m个数); 

m秒后,所有蚯蚓的长度(有n+m个数)。

【输入格式】

第1行包含6个整数n,m,q,u,v,t,其中:nmq的意义见例题讲解;uvt均为正整数;你需要自己计算p=u/v(保证0uv)的值;t是输出参数,其含义将会在输出格式中解释。

第2行包含n个非负整数,为 a1,a2,…,an,即初始时n只蚯蚓的长度。

同一行中相邻的两个数之间用一个空格分隔。

保证1n105,0m7×106,0uv109,0q200,1t71,0ai108

【输出格式】

第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]需要由大到小排序吗?

试根据以上分析,完成满分代码(指完成的代码可通过全部测试数据)。