记录编号	298363	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]开车旅行	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.926 s
提交时间	2016-08-20 20:45:24	内存使用	108.65 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
using namespace std;
const int N=200010,maxl=1000000000;
int n,m,h[N],A[N],level,s0,x0;
//a[i]表示到了i地，由B开车的目的地；a[i+n]表示到了i地，由A开车的目的地 
set<int> S;
map<int,int> M;
bool cmp(const int x,const int y){
	return abs(x-level)==abs(y-level)?x<y:abs(x-level)<abs(y-level);
}
int P(int x){return x>n?x-n:x;}
struct element{int f;long long a,b,l;}dp[N][20];
long long ansa,ansb;
void ask(int s0,int x0){
	long long ans=0;int i=19;
	ansa=ansb=0;
	while (1){
		while (i>=0&&dp[s0][i].l>x0) i--;
		if (i<0) break;
		ans+=dp[s0][i].l;
		ansa+=dp[s0][i].a;
		ansb+=dp[s0][i].b;
		x0-=dp[s0][i].l;
		s0=dp[s0][i].f;
	}
}
int main()
{
	freopen("drive.in","r",stdin);
	freopen("drive.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&h[i]),M[h[i]]=i;
	h[0]=-maxl;
	for (int i=n;i;i--){
		S.insert(level=h[i]);
		int q[4]={0},cnt=0;
		set<int>::iterator l=S.find(h[i]),r=l;
		for (int j=1;j<=2;j++){
			if (l==S.begin()) break;
			l--;q[++cnt]=*l;
		}
		for (int j=1;j<=2;j++){
			r++;
			if (r==S.end()) break;
			q[++cnt]=*r;
		}
		sort(q+1,q+cnt+1,cmp);
		if (cnt>=1) A[i]=M[q[1]]+n;
		if (cnt>=2) A[i+n]=M[q[2]];
	}
	for (int i=1;i<=n*2;i++){
		dp[i][0].f=A[i];
		if (i<=n) dp[i][0].b=abs(h[i]-h[P(A[i])]);
			else dp[i][0].a=abs(h[i-n]-h[A[i]]);
		dp[i][0].l=dp[i][0].a+dp[i][0].b;
	}
	for (int j=1;j<20;j++)
	for (int i=0;i<=n*2;i++){
		int fa=dp[i][j-1].f;
		dp[i][j].f=dp[fa][j-1].f;
		dp[i][j].l=dp[i][j-1].l+dp[fa][j-1].l;
		dp[i][j].a=dp[i][j-1].a+dp[fa][j-1].a;
		dp[i][j].b=dp[i][j-1].b+dp[fa][j-1].b;
	}
	
	//第一问 
	int ans=0;
	double Min=maxl;
	scanf("%d",&x0);
	for (s0=1;s0<=n;s0++){
		ask(s0+n,x0);
		if (Min==maxl){
			if (h[s0]>h[ans]||ansb==0) ans=s0;
			if (ansb!=0) ans=s0,Min=double(ansa)/ansb;
		}
		else{
			if (ansb!=0&&double(ansa)/ansb<Min)
				Min=double(ansa)/ansb,ans=s0;
		}
	}
	printf("%d\n",ans);
	
	//第二问 
	scanf("%d",&m);
	while (m--){
		scanf("%d%d",&s0,&x0);
		ask(s0+n,x0);
		printf("%lld %lld\n",ansa,ansb);
	}
	return 0;
}