JDOJ-3140: [NOIP2016]蚯蚓 D2 T2 手写堆 队列

[文章目录]

Description

本题中,我们将用符号⌊c⌋表示对c向下取整,例如:⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3

蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有n只蚯蚓(n为正整数)。每只蚯蚓拥有长度,我们设第i只蚯蚓的长度为ai(i=1,2,...,n),并保证所有的长度都是非负整数(即:可能存在长度为0的蚯蚓)。

每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数p(是满足0<p<1的有理数)决定,设这只蚯蚓长度为x,神刀手会将其切成两只长度分别为⌊px⌋x−⌊px⌋的蚯蚓。特殊地,如果这两个数的其中一个等于0,则这个长度为0的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加q(是一个非负整常数)。

蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要m秒才能到来......

(m为非负整数)

蛐蛐国王希望知道这m秒内的战况。具体来说,他希望知道:

•m秒内,每一秒被切断的蚯蚓被切断前的长度(有m个数)

•m秒后,所有蚯蚓的长度(有n+m个数)。

先不谈正解,先看看暴力怎么搞,mlog(n+m)堆啊。

然而,据说有STL并不能得多少分,所以让我们学习一下手写heap吧2333

上浮,下沉。感觉蛮容易的,交了一下,70!!!

另外10分是由于u/v的数据在10^9,中间算的时候必须先开下longlong。水水80。开心

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct heap
{
    int q[7200000];
    int now;
    heap() {now=0;}
    void down(int x)
    {
        int goal;
        while((x<<1|1)<=now&&(q[x]<q[x<<1]||q[x]<q[x<<1|1]))
        {
            goal=q[x<<1] > q[x<<1|1] ? x<<1 : x<<1|1;
            swap(q[x],q[goal]);
            x=goal;
        }
        if((x<<1)<=now&&q[x<<1]>q[x]) swap(q[x],q[x<<1]);
    }
    void up(int x)
    {
        while(x>1&&q[x]>q[x>>1])
            swap(q[x],q[x>>1]),x>>=1;
    }
    void pop() {q[1]=q[now];now--;down(1);}
    int top(){return q[1];}
    void push(int x){q[++now]=x;up(now);}
    bool empty(){return now==0;}
    int size(){return now;}
}q;
int n,m,val,u,v,t,now,cnt;
int read()
{
    int re=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
        re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re;
}
int main()
{
    n=read();m=read();val=read();u=read();v=read();t=read();
    for(int i=1;i<=n;i++) q.push(read());
    bool flag=1;
    for(int i=1;i<=m;i++)
    {
        int tmp=q.top();
        q.pop();
        if(i%t==0)
        {
            if(flag) printf("%d",tmp+now),flag=0;
            else printf(" %d",tmp+now);
        } 
        tmp+=now;
        now+=val;
        int c=1ll*tmp*u/v;//记住数据范围。
        q.push(c-now); q.push(tmp-c-now);
    }
    puts("");
    flag=1;
    while(!q.empty())
    {
        cnt++;
        if(cnt%t==0)
        {
            if(flag) printf("%d",q.top()+now),flag=0;
            else printf(" %d",q.top()+now);
        }
        q.pop();
    }
    puts("");
    return 0;
}

下面让我们聊一下正解。对于每次拿出来的蚯蚓,长度为i,切成两部分 i*u/v; i*(1-u/v).然后我们在拿出来一个蚯蚓,长度为j,显然 j-q<=i 然后我们分成了两部分 j*u/v ;j*(1-u/v),然后我们发现先前切得部分变成了i*u/v+q;i*(1-u/v)+q;则i*u/v+q>(j-q)*u/v+q=j*u/v+q-q*u/v > j*u/v 所以每次切成的两段都是单调递减的,所以我们维护三个个队列,两个作为每次用来维护切成两段的单调队列,一个是原数组,每次找到队列们第一个元素最大的那个拿出来,分成两段后放到两个单调队列里。保证3个队列的首元素中有一个肯定是最优解。(谁出的题??好机智)。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int tmp,now,c,goal;
int n,m,q,u,v,t;
int que[3][7200000];
int head[3],tail[3];
int read()
{
	int re=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9')
		re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
	return re;
}
bool cmp(int x,int y)
{
	return x>y;
}
void doit()
{
	int tmp=-1<<30;
	if(tail[1]>=head[1]&&tmp<que[1][head[1]]) goal=1,tmp=que[1][head[1]];
	if(tail[2]>=head[2]&&tmp<que[2][head[2]]) goal=2,tmp=que[2][head[2]];
	if(tail[0]>=head[0]&&tmp<que[0][head[0]]) goal=0;
}
int main()
{
	n=read();m=read();q=read();u=read();v=read();t=read();
	for(int i=1;i<=n;i++)
		scanf("%d",&que[0][i]);
	sort(que[0]+1,que[0]+n+1,cmp);
	head[0]=1,tail[0]=n;
	head[1]=head[2]=1;
	bool flag=1;
	for(int i=1;i<=m;i++)
	{
		doit();
		tmp=que[goal][head[goal]];
		head[goal]++;
		tmp+=now;
		if(!(i%t))
		{
			if(flag) printf("%d",tmp),flag=0;
			else printf(" %d",tmp);
		} 
		now+=q;
		c=1ll*tmp*u/v;
		que[1][++tail[1]]=c-now;
		que[2][++tail[2]]=tmp-c-now;
	}
	puts("");
	flag=1;
	for(int i=1;i<=n+m;i++)
	{
		doit();
		if(!(i%t))
		{
			if(flag) printf("%d",que[goal][head[goal]]+now),flag=0;
			else printf(" %d",que[goal][head[goal]]+now);
		}
		head[goal]++;
	}
	puts("");
	return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注