luoguP2827 蚯蚓

显而易见的,后切断的蚯蚓对\(\{a_i,a_j\}\)一定比先切断的蚯蚓对\(\{b_i,b_j\}\)小.即:
\[ \begin{align} a_i<b_i,a_j<b_j \end{align} \]
所以我们可以用三个队列,一个存放原来的蚯蚓,一个存放所有的\(x_i\),一个存放所有的\(x_j\).

每次对三个队头比较取最小值即可.

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define il inline
#define rg register
#define gi read<int>
#define mp make_pair
using namespace std;
typedef long long ll;
const int O = 1e5 + 10, inf = 2e9;
template<class TT>
il TT read() {
    TT o = 0,fl = 1; char ch = getchar();
    while (!isdigit(ch) && ch != '-') ch = getchar();
    if (ch == '-') fl = -1, ch = getchar();
    while (isdigit(ch)) o = o * 10 + ch - '0', ch = getchar();
    return fl * o;
}
struct Data {
    int v, id;
    il bool operator < (Data rhs) const {
        return v > rhs.v;
    }
} cmp[3];
queue<int> Q[3];
int n, m, q, u, v, t, x, top = 1, a[O];
int main() {
    n = gi(), m = gi(), q = gi(), u = gi(), v = gi(), t = gi();
    for (int i = 1; i <= n; ++i) a[i] = gi(); a[n + 1] = -inf;
    sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1);
    for (int i = 1; i <= m; ++i) {
        cmp[0] = (Data) { a[top], 0 };
        cmp[1] = (Data) { Q[1].empty() ? -inf : Q[1].front(), 1 };
        cmp[2] = (Data) { Q[2].empty() ? -inf : Q[2].front(), 2 };
        sort(cmp, cmp + 3); x = cmp[0].v;
//      printf("%d %d %d\n", cmp[0].v, cmp[1].v, cmp[2].v);
        if (!cmp[0].id) ++top;
        else Q[cmp[0].id].pop();
        x += (i - 1) * q;
        if (i % t == 0) printf("%d ", x);
        int A = 1ll * x * u / v, B = x - A;
//      printf("%d %d %d\n", A, B, cmp[0].id);
        A -= q * i, B -= q * i;
        Q[1].push(A), Q[2].push(B);
    }
    puts("");
    Q[1].push(-inf), Q[2].push(-inf);
    for (int i = 1; i <= n + m; ++i) {
        cmp[0] = (Data) { a[top], 0 };
        cmp[1] = (Data) { Q[1].front(), 1 };
        cmp[2] = (Data) { Q[2].front(), 2 };
        sort(cmp, cmp + 3);
        if (!cmp[0].id) x = a[top++];
        else x = Q[cmp[0].id].front(), Q[cmp[0].id].pop();
        if (i % t == 0) printf("%d ", x + m * q);
    }
    return 0;
}

luoguP2827 蚯蚓

原文：https://www.cnblogs.com/lylyl/p/11701105.html