35分做法

用堆来取最大值，暴力更新其余数的值。

65~85分做法

还是用堆来取最大值，其余的数增加可以变成新切开的两个数减少，最后统一加上一个数。

#include <queue>

#include <cstdio>

#include <iostream>

#include <algorithm>

#define LL long long

LL q, u, v;

int n, m, t;

std::priority_queue <LL> Q;

inline int read()

{

    int x = 0, f = 1;

    char ch = getchar();

    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

    for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

    return x * f;

}

int main()

{

    int i;

    LL x, y;

    n = read();

    m = read();

    q = read();

    u = read();

    v = read();

    t = read();

    for(i = 1; i <= n; i++)

    {

        x = read();

        Q.push(x);

    }

    for(i = 1; i <= m; i++)

    {

        if(i % t == 0) printf("%lld ", (LL)Q.top() + (i - 1) * q);

        x = (LL)(Q.top() + (i - 1) * q) * u / v;

        y = (LL)Q.top() + (i - 1) * q - x;

        Q.pop();

        Q.push(x - i * q);

        Q.push(y - i * q);

    }

    puts("");

    for(i = 1; i <= n + m; i++)

    {

        if(i % t == 0) printf("%lld ", (LL)Q.top() + m * q);

        Q.pop();

    }

    return 0;

}

100分做法

先排序。

将最大的切成两个小的分别放到另两个队列b和c里。

取最大值的话就从这3个队列的队头找最大的，切完后再放回b和c队列队尾。

这样b和c始终是单调递减。

同样，其余的增加可以换成切出来的另两个减少。

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 7000003

#define LL long long

#define max(x, y) ((x) > (y) ? (x) : (y))

#define Max(x, y, z) ((x) > max(y, z) ? (x) : max(y, z))

LL q, u, v, a[N], b[N], c[N];

int n, m, t, t1, t2 = 1, t3 = 1, cnt;

inline int read()

{

	int x = 0, f = 1;

	char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

	return x * f;

}

int main()

{

	int i;

	LL x, y;

	t1 = n = read();

	m = read();

	q = read();

	u = read();

	v = read();

	t = read();

	a[0] = -(~(1 << 31));

	memset(b, -127 / 3, sizeof(b));

	memset(c, -127 / 3, sizeof(c));

	for(i = 1; i <= n; i++) a[i] = read();

	std::sort(a + 1, a + n + 1);

	for(i = 1; i <= m; i++)

	{

		if(i % t == 0) printf("%lld ", Max(a[t1], b[t2], c[t3]) + (i - 1) * q);

		if(Max(a[t1], b[t2], c[t3]) == a[t1] && t1 >= 1)

		{

			cnt++;

			x = (a[t1] + (i - 1) * q) * u / v;

			y = a[t1] + (i - 1) * q - x;

			b[cnt] = x - i * q;

			c[cnt] = y - i * q;

			t1--;

		}

		else if(Max(a[t1], b[t2], c[t3]) == b[t2] && t2 <= cnt)

		{

			cnt++;

			x = (b[t2] + (i - 1) * q) * u / v;

			y = b[t2] + (i - 1) * q - x;

			b[cnt] = x - i * q;

			c[cnt] = y - i * q;

			t2++;

		}

		else

		{

			cnt++;

			x = (c[t3] + (i - 1) * q) * u / v;

			y = c[t3] + (i - 1) * q - x;

			b[cnt] = x - i * q;

			c[cnt] = y - i * q;

			t3++;

		}

	}

	puts("");

	for(i = 1; i <= n + m; i++)

	{

		if(i % t == 0) printf("%lld ", Max(a[t1], b[t2], c[t3]) + m * q);

		if(Max(a[t1], b[t2], c[t3]) == a[t1] && t1 >= 1) t1--;

		else if(Max(a[t1], b[t2], c[t3]) == b[t2] && t2 <= cnt) t2++;

		else t3++;

	}

	return 0;

}

由这个题可见还是得多挖掘题目给出的性质。

巴特西

[luoguP2827] 蚯蚓（堆？队列！）

35分做法

65~85分做法

100分做法

最新文章

热门文章