本题中，我们将用符号 $\lfloor c \rfloor$ 表示对 $c$ 向下取整，例如： $\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。
蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 $n$ 只蚯蚓（ $n$ 为正整数）。每只蚯蚓拥有长度，我们设第 $i$ 只蚯蚓的长度为 $a_i$（ $i = 1, 2, \ldots , n$），并保证所有的长度都是非负整数（即：可能存在长度为 $0$ 的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 $p$（是满足 $0 < p < 1$ 的有理数）决定，设这只蚯蚓长度为 $x$，神刀手会将其切成两只长度分别为 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ 的蚯蚓。特殊地，如果这两个数的其中一个等于 $0$，则这个长度为 $0$ 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 $q$（是一个非负整常数）。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 $m$ 秒才能到来 $\cdots \cdots$ （ $m$ 为非负整数）
蛐蛐国王希望知道这 $m$ 秒内的战况。具体来说，他希望知道：
$m$ 秒内，每一秒被切断的蚯蚓被切断前的长度（有 $m$ 个数）；
$m$ 秒后，所有蚯蚓的长度（有 $n + m$ 个数）。
蛐蛐国王当然知道怎么做啦！但是他想考考你 $\cdots \cdots $
题解
感觉平衡树要被卡，还是队列比较靠谱……
当 $q = 0$ 时，如果我们将每次切开后得到的蚯蚓分别放到两个序列中，则这两个序列都是单调的。将最初的蚯蚓排序，作为另一个序列。每次从三个序列中寻找最大值，删除，计算新蚯蚓插入到两个序列中即可。
当 $q \neq 0$ 时，每次只有两个新蚯蚓不增加长度，我们可以记录所有的蚯蚓被统一增加的长度，对每次不增加的减去这个长度。显然，单调性仍然满足。
时间复杂度为 $O(n \log n + m)$。
代码
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include <bits/stdc++.h>
using std::cin;
using std::cout;
char ch;
bool iosig;
template<class T>
inline void read(T &x) {
iosig = 0, x = 0;
do {
ch = getchar();
if (ch == '-') iosig = 1;
} while (!isdigit(ch));
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
if (iosig) x = -x;
}
const int MAXN = 100000;
const int MAXM = 7000000;
template<class T>
struct Queue {
T a[MAXN + MAXM], *l, *r;
Queue() : l(a), r(a - 1) {}
inline void push(const T &x) {
*++r = x;
}
inline void pop() {
l++;
}
inline T &front() {
return *l;
}
inline bool empty() const {
return l > r;
}
};
Queue<int> q[3];
inline int getMax() {
register int res = -1;
for (register int i = 0; i < 3; i++)
if (!q[i].empty() && (res == -1 || q[i].front() > q[res].front()))
res = i;
return res;
}
inline void solve() {
register int n, m, k, u, v, t;
read(n), read(m), read(k), read(u), read(v), read(t);
static int a[MAXN + 1];
for (register int i = 1; i <= n; i++) read(a[i]);
std::sort(a + 1, a + n + 1);
for (register int i = n; i >= 1; i--) q[0].push(a[i]);
register int d = 0;
for (register int i = 1; i <= m; i++) {
register int j = getMax();
register int x = q[j].front();
q[j].pop();
x += d;
if (i % t == 0) cout << x << " ";
register int a = static_cast<long long>(x) * u / v, b = x - a;
d += k;
a -= d, b -= d;
q[1].push(a), q[2].push(b);
}
cout << '\n';
for (register int i = 1; i <= n + m; i++) {
register int j = getMax();
register int x = q[j].front();
q[j].pop();
x += d;
if (i % t == 0) cout << x << " ";
}
}
int main() {
solve();
return 0;
}
|
