蚯蚓

题目描述

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

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

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

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

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

(m为非负整数)

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

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

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

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

输入输出格式

输入格式:

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

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

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

保证10^51≤n≤10^​5,0<m≤7∗10^​6​,0≤u<v≤10^9,​0≤q≤200,1≤t≤71,0<ai≤10^8.

输出格式:

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

第二行输出⌊(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

输入样例2

3 7 1 1 3 9

3 3 2

输出样例2

//空行

2

思路

由于每次切的都是最长的 所以且完后的长度都是递减的

我们可以维护三个队列第一个队列放未切的蚯蚓

第二和第三个队列放被切后的蚯蚓

每次切三个队列的中队首最大的一个

因为被切完后的蚯蚓一开始不会增长

我们可以记录一个ADD 表示到目前为止忽略被切的蚯蚓 其他蚯蚓一共增长了多少

每次往队列中放切后的蚯蚓时让当前长度减去ADD就可以了 这样再最后往外取出的时候 就可以直接让取出的长度增加ADD 就是目前的长度

注意:往队列中放的时候要减ADD 往外去的时候要加ADD


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#define INF (1 << 30)
#define LL long long
using namespace std;
inline LL Max(LL x, LL y) {return x >= y ? x : y;}
inline LL Min(LL x, LL y) {return x <= y ? x : y;}
LL n, m, q, u, v, t;
LL a[100005];
double p;LL ADD;
queue<LL> q1, q2, q3;
LL b[1000005];
LL get_Max()
{
LL x = -INF, y = -INF, z = -INF;
if (!q1.empty()) x = q1.front();
if (!q2.empty()) y = q2.front();
if (!q3.empty()) z = q3.front();
if (!q1.empty() && x >= y && x >= z) {q1.pop(); return x + ADD;}
if (!q2.empty() && y >= z) {q2.pop(); return y + ADD;}
if (!q3.empty()) {q3.pop(); return z + ADD;}
}
inline bool comp(LL x, LL y) {return x > y;}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &q, &u, &v, &t);
p = 1.0 * u / v;
for (LL i=1; i<=n; i++) scanf("%lld", &a[i]);
sort (a + 1, a + n + 1);
for (LL i=n; i>=1; i--) q1.push(a[i]);
for (LL i=1; i<=m; i++)
{
LL k = get_Max();
if (i % t == 0) printf("%lld ", k);
LL len = floor(k * p);
q2.push(Max(k-len-ADD-q,len-ADD-q));q3.push(Min(len-ADD-q,k-len-ADD-q));ADD += q;
}
printf("\n");
LL sum = 1;
while(!q1.empty() || !q2.empty() || !q3.empty())
{
LL k = get_Max();
if (sum % t == 0) printf("%lld ", k);
sum ++;
}
return 0;
}