洛谷 P2827 蚯蚓 题解

作者：岸芷汀兰

一、题目：

洛谷原题

二、思路：

---

1. 80分做法

优先队列
用priority_queue直接模拟即可。
需要注意的是，“其余蚯蚓的长度都会增加 q”的处理：其余增加q，两条不变，等价于两条减小q，其他不变。这样，每次分完一条蚯蚓后，将分成的两条蚯蚓的长度都减去q，同时更新删掉的总长度（del），那么原本的长度=优先队列中的长度+del。
代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>

using namespace std;
inline int read(void) {
    int x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0'&&ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f * x;
}

const int maxn = 1e5 + 5;

int n, m, q, u, v, t, a[maxn];

priority_queue<int>que;

int main()
{
    n = read(); m = read(); q = read(); u = read(); v = read(); t = read();
    for (register int i = 1; i <= n; i++) {
        a[i] = read();
        que.push(a[i]);
    }
    for (register int i = 1; i <= m; i++) {
        int x = que.top(); que.pop();
        x = x + (i - 1)*q;
        if (i%t == 0) {
            printf("%d ", x);
        }
        int a1 = (double)u / v * x; int a2 = x - a1;
        a1 = a1 - (i - 1)*q; a2 = a2 - (i - 1)*q;
        que.push(a1 - q); que.push(a2 - q);
    }
    puts("");
    int cnt = 0;
    while (que.size()) {
        cnt++;
        int x = que.top(); que.pop();
        if (cnt%t == 0) {
            printf("%d ", x + m * q);
        }
    }
    puts("");
    return 0;
}

---

2.满分做法：

找出题目中隐含的单调性。
设蚯蚓a被分成 a1,a2 $a_1,a_2$，蚯蚓b被分成 b1,b2 $b_1,b_2$,且a比b先分，则可以证明：

len[a1]>len[a2],len[b1]>len[b2] $$len[a_1]>len[a_2],len[b_1]>len[b_2]$$

∵ $\because$ a比b先分
∴len[a]>len[b] $\therefore len[a]>len[b]$
三个变量的单调性使得我们不需要用优先队列，只需用三个普通队列，分别存储
a,a1,a2 $a,a_1,a_2$ 即可，每次比较三个队列的队头大小输出。对于q的处理同80分做法。

三、代码：

#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>//头文件准备

using namespace std;

inline int read(void) {
    int x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0'&&ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f * x;
}

const int maxn = 1e5 + 5, maxm = 7e6 + 5;

int n, m, q, u, v, t, a[maxn], que[3][maxm], l[3], r[3], del;

int main() {
    n = read(); m = read(); q = read(); u = read(); v = read(); t = read();
    for (register int i = 1; i <= n; i++) {
        a[i] = read();
    }
    memset(que, 0x3f, sizeof que);
    memset(r, -1, sizeof r);
    sort(a + 1, a + n + 1, greater<int>());
    for (register int i = 1; i <= n; i++) {
        que[0][++r[0]] = a[i];
    }
    for (register int i = 1; i <= m; i++) {
        int now = -1 << 30, nowj;
        for (register int j = 0; j < 3; j++) {
            if (l[j] <= r[j] && que[j][l[j]] > now) {
                now = que[j][l[j]];
                nowj = j;
            }
        }
        l[nowj]++;
        if (i%t == 0) { printf("%d ", now + del); }
        que[1][++r[1]] = 1LL * (now + del)*u / v - del - q;
        que[2][++r[2]] = now + del - 1LL * (now + del)*u / v - del - q;
        del += q;
    }
    puts("");
    for (register int i = 1; i <= n + m; i++) {
        int now = -1 << 30, nowj;
        for (register int j = 0; j < 3; j++) {
            if (l[j] <= r[j] && que[j][l[j]] > now) {
                now = que[j][l[j]];
                nowj = j;
            }
        }
        if (i%t == 0)printf("%d ", del + now);
        l[nowj]++;
    }
    return 0;
}