洛谷p2827蚯蚓题解

题目

算法标签里的算法什么的都不会啊

什么二叉堆？？

qbxt出去学习的时候讲的，一段时间之前做的，现在才写到博客上的

维护3个队列，队列1表示最开始的蚯蚓，队列2表示每一次被切的蚯蚓被分开的较长的那一部分，队列3表示每一次被切的蚯蚓被分开的较短的那一部分。

我们先把原序列排序，因为不管怎么切，先被切的蚯蚓分成的两部分一定比后切的蚯蚓分成的两部分大

寻找每次切哪一只蚯蚓就是在队列1、队列2、队列3的队头找一个算上增加的长度最大的蚯蚓，之后把他出队，切开的两部分分别进入队2、队3。

最后合并输出

Code：

#include <queue>

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = ;

unsigned long long n, m, q, u, v, a[N], ans[N], s, y, tot, t;

queue<int>q1, q2, q3;

int cmp (long x, long y) {

    return x > y;

}

int maxn () {

    long long x1 = -( << ), x2 = x1, x3 = x1;

    if (!q1.empty ()) x1 = q1.front ();

    if (!q2.empty ()) x2 = q2.front ();

    if (!q3.empty ()) x3 = q3.front ();

    if (x1 >= x2 && x1 >= x3) {q1.pop (); return x1;}

    if (x2 >= x1 && x2 >= x3) {q2.pop (); return x2;}

    q3.pop ();return x3;

}

void putin (long long x1, long long x2) {

    if (x1 < x2) swap (x1, x2);

    q2.push(x1);

    q3.push(x2);

    return ;

}

int main () {

    scanf ("%lld%lld%lld%lld%lld%lld", &n, &m, &q, &u, &v, &t);

    for (long long i = ; i <= n; i++) scanf ("%lld", &a[i]);

    sort (a + , a +  + n, cmp);

    for (long long i = ; i <= n; i++) q1.push(a[i]);

    for (long long i = ; i <= m; i++) {

        ans[i] = maxn() + y;

        long long j = ans[i] * u / v, k = ans[i] - j;

        y += q;

        putin (j - y, k - y);

    }

    while (!q1.empty () || !q2.empty () || !q3.empty ()) a[++tot] = maxn() + y;

    for (long long i = t; i <= m; i += t) printf ("%lld ", ans[i]);

    printf ("\n");

    for (long long i = t; i <= tot; i += t) printf ("%lld ", a[i]);

    return ;

}

谢谢收看，祝身体健康!

巴特西

洛谷p2827蚯蚓题解

最新文章

热门文章