简答题 偏难
#23254

蚯蚓 【问题描述】 本题中,我们将用符号 表示对c向下取整,例如: 蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯…

蚯蚓

【问题描述】

本题中,我们将用符号表示对c向下取整,例如:

蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

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

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

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

蛐蛐国王希望知道这 m秒内的战况。具体来说,他希望知道:

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

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

蛐蛐国王当然知道怎么做啦!但是他想考考你……

【输入格式】

从文件earthworm.in中读入数据。

第一行包含六个整数 n , m , q , u , v , t 其中:n , m , q的意义见【问题描述】;u , v , t均为正整数;你需要自己计算 p = u / v(保证 0 < u < v)t 是输出参数,其含义将会在【输出格式】中解释。

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

同一行中相邻的两个数之间,恰好用一个空格隔开。

【输出格式】

输出到文件earthworm.out中。

第一行输出个整数,按时间顺序,依次输出第 t 秒,第 2t 秒,第 3t 秒,……被切断蚯蚓(在被切断前)的长度。

第二行输出个整数,输出 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。

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与上个数据不同。只需在每行都改为每两个数输出一个数即可。

虽然第一行最后有一个6 没有被输出,但是第二行仍然要重新从第二个数再开始输出。

【样例3输入】

3 7 1 1 3 9

3 3 2

【样例3输出】

2

【样例3说明】

这个数据中只有t=9与上个数据不同。

注意第一行没有数要输出,但也要输出一个空行。

【子任务】

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include &lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">double m,Q,u,v;</p><p style="text-align: left;">int t,n;</p><p style="text-align: left;">int cnt=0,tot=0,num=1;</p><p style="text-align: left;">double p;</p><p style="text-align: left;">int dd;</p><p style="text-align: left;">int ans1[(int)7e6+5];</p><p style="text-align: left;">int a[(int)7e6+5];</p><p style="text-align: left;">queue&lt;int&gt;q1;</p><p style="text-align: left;">queue&lt;int&gt;q2;</p><p style="text-align: left;">queue&lt;int&gt;q3;</p><p style="text-align: left;">inline int read() {</p><p style="text-align: left;"><span style="white-space:pre"> </span>int X = 0, F = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>char C = getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while (C &lt; '0' || C&gt;'9') {</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (C == '-') {</p><p style="text-align: left;"><span style="white-space:pre"> </span>F = -1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>C = getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>while (C &gt;= '0' &amp;&amp; C &lt;= '9') {</p><p style="text-align: left;"><span style="white-space:pre"> </span>X = (X &lt;&lt; 3) + (X &lt;&lt; 1) + C - '0';</p><p style="text-align: left;"><span style="white-space:pre"> </span>C = getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return X * F;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void write(int N) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (N &lt; 0) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>putchar('-');</p><p style="text-align: left;"><span style="white-space:pre"> </span>N = -N;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (N &gt;= 10) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>write(N / 10);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>putchar(N % 10 + '0');</p><p style="text-align: left;">}</p><p style="text-align: left;">inline int Get() {</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x1=INT_MIN,x2=INT_MIN,x3=INT_MIN;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!q1.empty())</p><p style="text-align: left;"><span style="white-space:pre"> </span>x1=q1.front();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!q2.empty())</p><p style="text-align: left;"><span style="white-space:pre"> </span>x2=q2.front();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!q3.empty())</p><p style="text-align: left;"><span style="white-space:pre"> </span>x3=q3.front();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x1&gt;=x2&amp;&amp;x1&gt;=x3) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>q1.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>} else if(x2&gt;=x3) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>q2.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x2;</p><p style="text-align: left;"><span style="white-space:pre"> </span>} else {</p><p style="text-align: left;"><span style="white-space:pre"> </span>q3.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x3;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}//那个公式</p><p style="text-align: left;">int main() {</p><p style="text-align: left;"><span style="white-space:pre"> </span>n=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>m=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>Q=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>u=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>v=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>t=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>p=(double)u/v;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(register int i=1; i&lt;=n; ++i) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans1[i]=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>sort(ans1+1,ans1+n+1, greater&lt;int&gt;());//排序后再压入</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(register int i=1;i&lt;=n;i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>q1.push(ans1[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>int tag=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(register int i=1; i&lt;=m; ++i) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>int d=Get();</p><p style="text-align: left;"><span style="white-space:pre"> </span>d+=tag;</p><p style="text-align: left;"><span style="white-space:pre"> </span>a[i]=d;</p><p style="text-align: left;"><span style="white-space:pre"> </span>int tad=d*p;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q2.push(tad-tag-Q);//截断后的第一节</p><p style="text-align: left;"><span style="white-space:pre"> </span>q3.push(d-tad-tag-Q);//第二节</p><p style="text-align: left;"><span style="white-space:pre"> </span>tag+=Q;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(register int i=t; i&lt;=m; i+=t) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>write(a[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf(" ");</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>puts("");</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(!q1.empty()||!q2.empty()||!q3.empty()) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>int u=Get();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(num%t==0) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>write(u+tag);//因为前面减了一个tag,现在加上</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf(" ");</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p><br style="text-align: left;"/></p><p style="text-align: left;"><span style="white-space:pre"> </span>num++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。