「Luogu 2827」蚯蚓

题面太长了就不蒯了

Luogu

分析

首先是 80pts 算法：用一点技巧模拟就好了~(≧▽≦)/~

然后是 100pts 算法。容易发现(其实是懒得证明)先被切割的蚯蚓分成的长度一定不小于后被切割的蚯蚓分成的长度，也就是具有一定单调性，所以我们建立 3 个队列，一个储存原数组，一个储存被切割的长度较小的蚯蚓长度，一个储存被切割的长度较大的蚯蚓长度，然后我们每次直接把切割的蚯蚓分成的两段放到队列里就好了，省掉了 log 的复杂度，其余的和 80pts 算法一样。

代码

80pts

//=========================
//  author:tyqs
//  date:2019.11.26
//  website:http://tyqs.kim
//=========================
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 7000001
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

struct earthworm {
    int len, tg;
    friend bool operator < (earthworm x, earthworm y) { return x.len + x.tg < y.len + y.tg; }
};

priority_queue <earthworm> cre;

double p;
int n, m, q, u, v, t, s;
int a[N];

int main() {
    read(n), read(m), read(q), read(u), read(v), read(t);
    p = 1.0 * u / v;
    for (int i = 1; i <= n; ++i) read(u), cre.push((earthworm){u, 0});
    for (int i = 1; i <= m; ++i) {
        u = cre.top().len, v = cre.top().tg;
        u += s + v, s += q, cre.pop();
        if (i % t == 0) printf("%d ", u);
    int k = p * u;
        cre.push((earthworm){k, -s}), cre.push((earthworm){u - k, -s});
    }
    puts("");
    int cnt = 0;
    while (!cre.empty()) {
        u = cre.top().len + s + cre.top().tg;
        cre.pop(); cnt++;
        if (cnt % t == 0) printf("%d ", u);
    }
    puts("");
    return 0;
}

100pts

//=========================
//  author:tyqs
//  date:2019.11.26
//  website:http://tyqs.kim
//=========================
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 8000001
#define il inline
#define re register
#define INF 0x3f3f3f3f
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

double p;
int n, m, q, u, v, t, s;
int a[N], ans[N];

queue <int> q1, q2, q3;

bool cmp(int x, int y) { return x > y; }

int getmax() {
    int x, y, z;
    x = y = z = -INF;
    if (!q1.empty()) x = q1.front();
    if (!q2.empty()) y = q2.front();
    if (!q3.empty()) z = q3.front();
    if (x >= y && x >= z) { q1.pop(); return x; }
    if (y >= x && y >= z) { q2.pop(); return y; }
    if (z >= x && z >= y) { q3.pop(); return z; }
}

void insert(int x, int y) {
    if (x > y) q2.push(x), q3.push(y);
    else q2.push(y), q3.push(x);
}

int main() {
    read(n), read(m), read(q), read(u), read(v), read(t);
    for (int i = 1; i <= n; ++i) read(a[i]);
    p = 1.0 * u / v;
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; ++i) q1.push(a[i]);
    for (int i = 1; i <= m; ++i) {
    int k = getmax();
    k += s, s += q;
    if (i % t == 0) printf("%d ", k);
    int tmp = k * p;
    insert(tmp - s, k - tmp - s);
    }
    puts(""), n = 0;
    while (!q1.empty() || !q2.empty() || !q3.empty()) a[++n] = getmax() + s;
    for (int i = t; i <= n; i += t) printf("%d ", a[i]);
    putchar('\n');
    return 0;
}

「Luogu 2827」蚯蚓

原文：https://www.cnblogs.com/hlw1/p/12260594.html