洛谷 P2827 蚯蚓 题解

时间:2023-01-01 18:40:39

作者:岸芷汀兰

一、题目:

洛谷原题

二、思路:


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被分成 a 1 , a 2 ,蚯蚓b被分成 b 1 , b 2 ,且a比b先分,则可以证明:

l e n [ a 1 ] > l e n [ a 2 ] , l e n [ b 1 ] > l e n [ b 2 ]

a比b先分
l e n [ a ] > l e n [ b ]
三个变量的单调性使得我们不需要用优先队列,只需用三个普通队列,分别存储
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;
}