NOIP 2016 蚯蚓题解

一道有趣的题目，首先想到合并果子，然而发现会超时，我们可以发现首先拿出来的切掉后比后拿出来切掉后还是还长，即满足单调递增，故建立三个队列即可。

代码

#include<bits/stdc++.h>

#define p u/v

using namespace std;

long long n,m,len,t,a,u,v;

const int maxn=1e7+10;

int line1[maxn],line2[maxn],line3[maxn];

int l1,l2,l3,r1,r2,r3;

bool cmp(int x,int y){

    return x>y;

}

int gots(int x){

    int a,b,c,d;

    a=b=c=d=-1;

    if(l1<=r1) b=line1[l1]+x*len;

    if(l2<=r2) c=line2[l2]+x*len;

    if(l3<=r3) d=line3[l3]+x*len;

    a=max(b,max(c,d));

    if(a==b) l1++;

    else{

        if(a==c) l2++;

        else l3++;

    }

    return a;

}

int main(){

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

    for(int i=1;i<=n;i++) scanf("%d",&line1[i]);

    sort(line1+1,line1+1+n,cmp);

    r1=n;l1=l2=l3=1;

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

        int x=gots(i-1);

        if(!(i%t)) printf("%d ",x);

        int a=x*p;

        int b=x-a;

        line2[++r2]=a-i*len;

        line3[++r3]=b-i*len;

    }printf("\n");

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

        int x=gots(m);

        if(!(i%t)) printf("%d ",x);

    }

    return 0;

}

巴特西

NOIP 2016 蚯蚓题解

最新文章

热门文章

巴特西

NOIP 2016 蚯蚓 题解

最新文章

热门文章

NOIP 2016 蚯蚓题解