题解 | 蚯蚓题解

很有意思的一道题。对于每秒的增长，因为是个定值，所以显然可以打标记处理，记录每只蚯蚓被切断的时间 $time$ ，那么这只增长量就是 $(i-time)*q$ ，可以利用一个堆来维护当前的最大长度，那么可以做到 $O(n+mlog(n+m))$ ，这样子已经可以通过 $75~8$ 5分了（卡常卡的好一点就85）。
这题最有意思的地方就是按题目规则切出来的蚯蚓都是有单调性的。对于当前切出来的两只蚯蚓，长的那一条一定比后面切出来的长的蚯蚓长，短的同理（因为增长量是一样的，而当前找的又是最长的那条来切），所以可以维护三个队列，一个放原来的蚯蚓，一个放切出来的长的蚯蚓，一个放切出来的短的蚯蚓，然后每次选一个最长的那个出来切。然后第二次输出的时候类似归并排序那样两个指针扫一扫，就能 $O(n+m)$ 合并三个队列，于是复杂度是严格 $O(nlogn + n + m)$ 的。不过实际上最后一步用个堆应该也可以卡过去。但是就没意思了。

#include <bits/stdc++.h>
using namespace std;

const int N = 7100010;
int n, m, q, u, v, t;
int a[100010], b[N][2], c[N][2], d[N], f[N];
int l[3], r[3];

int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1);
    l[0] = 1; r[0] = n;
    l[1] = 1; r[1] = 0;
    l[2] = 1; r[2] = 0;
    for(int i = 0; i < m; ++i) {
        int ans = 0, nx, ny;
        if(l[0] > r[0]) {
            if(l[1] <= r[1] && b[l[1]][0] + (i - b[l[1]][1]) * q >= c[l[2]][0] + (i - c[l[2]][1]) * q) ans = b[l[1]][0] + (i - b[l[1]][1]) * q, ++l[1];
            else ans = c[l[2]][0] + (i - c[l[2]][1]) * q, ++l[2];
        } else {
            if(a[l[0]] + i * q >= b[l[1]][0] + (i - b[l[1]][1]) * q && a[l[0]] + i * q >= c[l[2]][0] + (i - c[l[2]][1]) * q) ans = a[l[0]] + i * q, ++l[0];
            else if(b[l[1]][0] + (i - b[l[1]][1]) * q >= a[l[0]] + i * q && b[l[1]][0] + (i - b[l[1]][1]) * q >= c[l[2]][0] + (i - c[l[2]][1]) * q) ans = b[l[1]][0] + (i - b[l[1]][1]) * q, ++l[1];
            else ans = c[l[2]][0] + (i - c[l[2]][1]) * q, ++l[2];
        }
        nx = 1LL * ans * u / v; ny = ans - nx;
        if(nx < ny) swap(nx, ny);
        b[++r[1]][0] = nx; b[r[1]][1] = i + 1;
        c[++r[2]][0] = ny; c[r[2]][1] = i + 1;
        if((i + 1) % t == 0) printf("%d ", ans);
    }
    puts(""); int lim = m, cnt = 0;
    while(l[0] <= r[0] || l[1] <= r[1]) {
        if(l[0] <= r[0] && a[l[0]] + q * lim >= b[l[1]][0] + q * (lim - b[l[1]][1])) d[++cnt] = a[l[0]] + q * lim, ++l[0];
        else d[++cnt] = b[l[1]][0] + q * (lim - b[l[1]][1]), ++l[1];
    }
    int tot = 0, cur = 1;
    while(cur <= cnt || l[2] <= r[2]) {
        if(d[cur] >= c[l[2]][0] + (lim - c[l[2]][1]) * q) f[++tot] = d[cur++];
        else f[++tot] = c[l[2]][0] + (lim - c[l[2]][1]) * q, ++l[2];
        if(tot % t == 0) printf("%d ", f[tot]);
    }
    puts("");
    return 0;
}