题解
双向链表加倍增。。。
正写着不一定能写对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("%d ",ans); else printf("%d ",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 %lld ",disa,disb); } }