这道坑爹题调了我2小时233~
首先这道题可以用set，平衡树，双向链表等一堆非（sang）常（xin）简（bing）单（kuang）的算法搞出对于任何一个高度h[i]的前2名和后2名
然后我们看到这个
就想到了倍增。。。
但是调不出来o(≧口≦)o
还要特判一下A走后B就不走了的情况。。（用va[i][0]表示）
然后第一问O（N）。。第二问O（M）
最后在黄学长的blog的帮助之下才调了出来。。
真是zxyer说的纯模拟大水比题目啊（233~）
简直跟A*八数码有的一拼。。
下面贴代码
#include<iostream>
#include<set>
#include<map>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define inf 5000000000LL
using namespace std;
int h[100005];
int fa[100005],fb[100005];
long long a[100005],b[100005],va[100005][17],vb[100005][17],to[100005][17];
int n,m;
struct data{
long long key,h;
}t[5];
inline bool operator<(data a,data b)
{
return a.key<b.key||(a.key==b.key&&a.h<b.h);
}
set <long long> q;
map <long long,int> mp;
void pre(){
for(int i=n;i;i--)
{
q.insert(h[i]);
t[1].h=*--q.lower_bound(h[i]);t[2].h=*q.upper_bound(h[i]);
if(t[1].h!=-inf)t[3].h=*--q.lower_bound(t[1].h);
else t[3].h=-inf;
if(t[2].h!=inf)t[4].h=*q.upper_bound(t[2].h);
else t[4].h=inf;
for(int k=1;k<=4;k++)
t[k].key=abs(t[k].h-h[i]);
sort(t+1,t+5);
a[i]=t[2].key;fa[i]=mp[t[2].h];
b[i]=t[1].key;fb[i]=mp[t[1].h];
for(int j=0;j<=16;j++)
if(j==0)
{
if(fa[i]){va[i][0]=a[i];to[i][0]=fa[i];}
}
else if(j==1)
{
if(fb[fa[i]]){va[i][1]=a[i];vb[i][1]=b[fa[i]];to[i][1]=fb[fa[i]];}
}
else
if(to[to[i][j-1]][j-1])
{
va[i][j]=va[i][j-1]+va[to[i][j-1]][j-1];
vb[i][j]=vb[i][j-1]+vb[to[i][j-1]][j-1];
to[i][j]=to[to[i][j-1]][j-1];
}
else break;
}
}
double cal1(int x,int val)
{
int t1=0,t2=0;
for(int i=16;i>=0;i--)
if(to[x][i]&&t1+va[x][i]+vb[x][i]+t2<=val)
{
t1+=va[x][i];t2+=vb[x][i];
x=to[x][i];
}
if(t2==0)return inf;
return (double)t1/(double)t2;
}
void cal2(int x,int val)
{
int t1=0,t2=0;
for(int i=16;i>=0;i--)
if(to[x][i]&&t1+va[x][i]+vb[x][i]+t2<=val)
{
t1+=va[x][i];
t2+=vb[x][i];
x=to[x][i];
}
printf("%d %d
",t1,t2);
}
void solve1(){
double mn=1e60;int ans;
int num;
scanf("%d",&num);
for(int i=1;i<=n;i++)
{
double t=cal1(i,num);
if(t<mn||t==mn&&h[i]>h[ans])
{
mn=t;
ans=i;
}
}
printf("%d
",ans);
}
void solve2(){
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int s,x;
scanf("%d%d",&s,&x);
cal2(s,x);
}
}
int main(){
scanf("%d",&n);
q.insert(-inf);q.insert(inf);
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
mp[h[i]]=i;
}
pre();
solve1();
solve2();
return 0;
}