【NOIP2012】旅行计划

 

题解

双向链表加倍增。。。

正写着不一定能写对2333

 

终于写对了。。。

然而我的双向链表和别人的都不一样。。。

瑟瑟发抖。。。

代码

 

//by 减维
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<map>
#include<algorithm>
#define ll long long
#define inf (9223372036854775807LL)
using namespace std;

struct biao{
    int i,to,fr;
    ll v;
}e[100005];

int n,m,hest,ys[100005],zj[100005],cj[100005],f[100005][33];
ll x,her,a[100005][33],b[100005][33],h[100005];

bool cmp(const biao&x,const biao&y){return x.v>y.v;}
bool cm2(const biao&x,const biao&y){return x.i<y.i;}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&e[i].v),e[i].i=i,h[i]=e[i].v;
        if(h[i]>her) her=h[i],hest=i;
    }
    sort(e+1,e+n+1,cmp);
    for(int i=1;i<=n;++i)
        e[i].fr=e[i-1].i,e[i].to=e[i+1].i;
    sort(e+1,e+n+1,cm2);
    for(int i=1;i<=n;++i)
    {
        ll m1=inf,m2=inf,hh[5];int pos[5],a1,a2;
        
        hh[1]=abs(h[i]-h[e[i].fr]);                    pos[1]=e[i].fr;
        hh[2]=abs(h[i]-h[e[e[i].fr].fr]);              pos[2]=e[e[i].fr].fr;
        hh[3]=abs(h[i]-h[e[i].to]);                    pos[3]=e[i].to;
        hh[4]=abs(h[i]-h[e[e[i].to].to]);           pos[4]=e[e[i].to].to;
        
        if(e[i].fr==0)hh[1]=inf;
        if(e[e[i].fr].fr==0)hh[2]=inf;
        if(e[i].to==0)hh[3]=inf;
        if(e[e[i].to].to==0)hh[4]=inf;
        
        for(int j=1;j<=4;++j)
            if(m1>hh[j]||(m1==hh[j]&&h[a1]>h[pos[j]]))m2=m1,a2=a1,m1=hh[j],a1=pos[j];
        else
            if(m2>hh[j]||(m2==hh[j]&&h[a2]>h[pos[j]]))m2=hh[j],a2=pos[j];
        
        if(m1!=inf)zj[i]=a1;
        if(m2!=inf)cj[i]=a2;
        if(e[i].fr!=0)e[e[i].fr].to=e[i].to;
        if(e[i].to!=0)e[e[i].to].fr=e[i].fr;
        
    }
    for(int i=1;i<=n;++i)
    {
        f[i][0]=zj[cj[i]];
        if(i<=n-2)
            a[i][0]=abs(h[i]-h[cj[i]]);
        if(i<=n-1)
            b[i][0]=abs(h[cj[i]]-h[zj[cj[i]]]);
    }
    for(int i=1;i<=22;++i)
        for(int j=1;j<=n;++j)
        {
            f[j][i]=f[f[j][i-1]][i-1];
            a[j][i]=a[j][i-1]+a[f[j][i-1]][i-1];
            b[j][i]=b[j][i-1]+b[f[j][i-1]][i-1];
        }
    
    scanf("%lld",&x);
    int ans=1;
    double m1=inf;
    ll mh=-1;
    for(int i=1;i<=n;++i)
    {
        int pos=i;
        ll l=x,disa=0,disb=0;
        for(int j=22;j>=0;--j)
        {
            if(f[pos][j]!=0&&a[pos][j]+b[pos][j]<=l)
            {
                disa+=a[pos][j];
                disb+=b[pos][j];
                l-=a[pos][j]+b[pos][j];
                pos=f[pos][j];
            }
        }
        if(a[pos][0]<=l){
            disa+=a[pos][0];
            l-=a[pos][0];
        }
        double c=inf;
        if(disb==0) c=inf;
        else c=disa*1.0/disb;
        if(c<m1||(c==m1&&h[i]>mh))
        {
            m1=c;
            mh=h[i];
            ans=i;
        }
    }
    if(m1!=inf)printf("%dn",ans);
    else printf("%dn",hest);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        int s;
        scanf("%d%lld",&s,&x);
        int pos=s;
        ll l=x,disa=0,disb=0;
        for(int j=22;j>=0;--j)
        {
            if(f[pos][j]!=0&&a[pos][j]+b[pos][j]<=l)
            {
                disa+=a[pos][j];
                disb+=b[pos][j];
                l-=a[pos][j]+b[pos][j];
                pos=f[pos][j];
            }
        }
        if(a[pos][0]<=l){
            disa+=a[pos][0];
            l-=a[pos][0];
        }
        printf("%lld %lldn",disa,disb);
    }
}