题目大意：初始时有 $n$ 只蚯蚓，$m$ 次操作，每次取出最长的蚯蚓，设其长度为 $x$，然后把它砍成长度分别为 $\lfloor px \rfloor$ 和 $x-\lfloor px \rfloor$ 的两段，与此同时，其他蚯蚓的长度全部增长 $q$，问每次取出的蚯蚓长度是多少，以及最终的 $n+m$ 只蚯蚓的长度。$n \leq 10^5,m\leq 7 \times 10^6$
假设当前有两只蚯蚓，长度分别为 $x$ 和 $y$，其中 $x>y$，以下是前两秒的变化情况：
我们发现，$\lfloor px \rfloor + q > \lfloor p(y+q) \rfloor$ 且 $x - \lfloor px \rfloor + q \geq y + q - \lfloor p(y+q) \rfloor$
前者显然，后者的证明如下：
因为 $p<1$，所以
因为 $\lfloor p(x-y) \rfloor \leq \lfloor px \rfloor - \lfloor py \rfloor$ 且最多比 $\lfloor px \rfloor - \lfloor py \rfloor$ 小 $1$，所以
又因为 $\lfloor{pq}\rfloor \geq 0$，所以
因为 $\lfloor p(y+q) \rfloor \geq \lfloor py \rfloor + \lfloor pq \rfloor$ 且最多比 $\lfloor py \rfloor + \lfloor pq \rfloor$ 大 $1$，所以
即
于是开三个单调队列，一个保存 $x$，一个保存 $\lfloor px \rfloor$，另一个保存 $x - \lfloor px \rfloor$，那么这三个队列都是单调不增的。
记录每只蚯蚓被放入队列的时间，那么它与当前时间的差值乘上 $q$ 就是该蚯蚓在当前队列中增长的长度，每次从三个队首各取出一只蚯蚓比较，比较和砍断的时候先加上应该增长的值即可。
- 注意空间应该开到 $N+M$
- 下取整要用 $floor$，强制类型转换会出奇奇怪怪的错误（尽量少用）
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
const int N = 7100005; //注意应该开到N+M
struct Node {
int len, sec;
bool operator < (const Node &rhs) const {
return len > rhs.len;
}
} a[N], b[N], c[N];
int n, m, q, u, v, t, h1, t1, h2, t2, h3, t3;
double p;
int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
int main() {
scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
p = u * 1.0 / v;
for (int i = 1; i <= n; ++i) a[t1++].len = read();
std::sort(a, a + t1);
for (int i = 1; i <= m; ++i) {
int aa = h1 < t1 ? a[h1].len + (i - a[h1].sec - 1) * q : -1,
bb = h2 < t2 ? b[h2].len + (i - b[h2].sec - 1) * q : -1,
cc = h3 < t3 ? c[h3].len + (i - c[h3].sec - 1) * q : -1;
if (aa >= bb && aa >= cc) {
++h1;
b[t2++] = (Node){floor(aa * p), i};
c[t3++] = (Node){aa - floor(p * aa), i};
if (i % t == 0) printf("%d ", aa);
} else if (bb >= aa && bb >= cc) {
++h2;
b[t2++] = (Node){floor(p * bb), i};
c[t3++] = (Node){bb - floor(p * bb), i};
if (i % t == 0) printf("%d ", bb);
} else if (cc >= aa && cc >= bb) {
++h3;
b[t2++] = (Node){floor(p * cc), i};
c[t3++] = (Node){cc - floor(p * cc), i};
if (i % t == 0) printf("%d ", cc);
}
}
puts("");
for (int i = 1; i <= n + m; ++i) {
int aa = h1 < t1 ? a[h1].len + (m - a[h1].sec) * q : -1,
bb = h2 < t2 ? b[h2].len + (m - b[h2].sec) * q : -1,
cc = h3 < t3 ? c[h3].len + (m - c[h3].sec) * q : -1;
if (aa >= bb && aa >= cc) {
++h1;
if (i % t == 0) printf("%d ", aa);
} else if (bb >= aa && bb >= cc) {
++h2;
if (i % t == 0) printf("%d ", bb);
} else if (cc >= aa && cc >= bb) {
++h3;
if (i % t == 0) printf("%d ", cc);
}
}
puts("");
return 0;
}
时间复杂度 $O(m)$