洛谷P2827 蚯蚓

pts85/90（90应该是个意外，第一次交是90之后都是85了）：

优先队列模拟题意

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

int n,m,q,u,v,t,tim;

double p;

priority_queue<int>qq;

int main()

{

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

    p=1.0*u/(1.0*v);

    for(int i=,x;i<=n;i++){

        scanf("%d",&x);

        qq.push(x);

    }

    while(m--){

        tim++;

        int x=qq.top();

        qq.pop();

        if(tim%t==)printf("%d ",x+(tim-)*q);

        int y=(int)(p*(double)(x+(tim-)*q));

        x=(x+(tim-)*q)-y;

        qq.push(x-tim*q),qq.push(y-tim*q);

    }

    printf("\n");

    int now=;

    while(qq.size()){

        now++;

        if(now%t==){

            printf("%d ",qq.top()+tim*q);

        }

        qq.pop();

    }

    return ;

}

优先队列

顺手练一下手写二叉堆

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,q,u,v,t,tim,a[*],num;

double p;

bool cmp(int x,int y){

    return x>y;

}

int main()

{

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

    p=1.0*u/(1.0*v);

    for(int i=,x;i<=n;i++){

        scanf("%d",&a[i]);

        x=i;

        while(x>&&a[x]>a[x>>]){

            swap(a[x],a[x>>]);

            x>>=;

        }

    }

    while(m--){

        tim++;

        int x=a[];

        if(tim%t==)printf("%d ",x+(tim-)*q);

        int y=(int)(p*(double)(x+(tim-)*q));

        x=(x+(tim-)*q)-y;

        a[]=x-tim*q;

        int now=;

        while((a[now]<a[now<<]||a[now]<a[now<<|])&&(now<<|)<=n){

            if(a[now<<]<a[now<<|]){

                swap(a[now],a[now<<|]);

                now<<=;

                now|=;

            }

            else{

                swap(a[now],a[now<<]);

                now<<=;

            }

        }

        if(a[now]<a[now<<]&&(now<<)<=n){

            swap(a[now],a[now<<]);

        }

        a[++n]=y-tim*q;

        now=n;

        while(now>&&a[now]>a[now>>]){

            swap(a[now],a[now>>]);

            now>>=;

        }

    }

    printf("\n");

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

    for(int i=;i<=n;i++){

        if(i%t==){

            printf("%d ",a[i]+tim*q);

        }

    }

    return ;

}

手写二叉堆

正解：

发现先切的蚯蚓产生的长段永远不小于后切的蚯蚓产生的长段，短段也是。因为从准备切先切的开始，后切的生长t个单位长度的同时，先前切好的两段都生长了t-1个单位长度。

切好的长段集合和短段集合本身就具有单调性。

用三个队列分别储存未切的，切好的长段，切好的短段，每次从三个队头寻找最大的进行操作。

#include<iostream>

#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

int n,m,q,u,v,t,tim,maxx,pos,a[*],inf=;

double p;

queue<int>qq[];

bool cmp(int x,int y){

    return x>y;

}

int main()

{

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

    p=1.0*u/(1.0*v);

    for(int i=;i<=n;i++){

        scanf("%d",&a[i]);

    }

    sort(a+,a+n+);

    for(int i=n;i>=;i--)qq[].push(a[i]);

    while(m--){

        tim++;

        maxx=pos=-inf;

        if(qq[].front()>maxx&&qq[].size())maxx=qq[].front(),pos=;

        if(qq[].front()>maxx&&qq[].size())maxx=qq[].front(),pos=;

        if(qq[].front()>maxx&&qq[].size())maxx=qq[].front(),pos=;

        qq[pos].pop();

        if(tim%t==)printf("%d ",maxx+(tim-)*q);

        int y=(int)(p*(double)(maxx+(tim-)*q));

        maxx=(maxx+(tim-)*q)-y;

        qq[].push(max(maxx,y)-tim*q),qq[].push(min(maxx,y)-tim*q);

    }

    printf("\n");

    n=;

    while(qq[].size()){

        a[++n]=qq[].front();

        qq[].pop();

    }

    while(qq[].size()){

        a[++n]=qq[].front();

        qq[].pop();

    }

    while(qq[].size()){

        a[++n]=qq[].front();

        qq[].pop();

    }

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

    for(int i=;i<=n;i++){

        if(i%t==){

            printf("%d ",a[i]+tim*q);

        }

    }

    return ;

}

巴特西

洛谷P2827 蚯蚓

最新文章

热门文章