首页 > 代码库 > [luoguP2827] 蚯蚓（堆？队列！）

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

2024-11-15 16:45:02   203人阅读

传送门

 

35分做法

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

 

65~85分做法

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

#include <queue>#include <cstdio>#include <iostream>#include <algorithm>#define LL long longLL 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] 蚯蚓（堆？队列！）


联系
我们