记录编号	197693	评测结果	AAAAAAAAAAAAAAWWWWWW
题目名称	[NOIP 2012]开车旅行	最终得分	70
用户昵称	forever	是否通过	未通过
代码语言	C++	运行时间	3.756 s
提交时间	2015-10-24 11:23:21	内存使用	16.35 MiB

#include<cstdio>
#include<cmath>
using namespace std;
int x[100010],s[100010],dis[2002][2002],flag;
int Ans_A,Ans_B,X;
double Ans=10000000010.00;
int n,Q,h[1002];
void Get_Ans1(int si,int id){/*1---->A,2----->B*/
	long long Maxx=10000000010;
	long long Max_second=10000000010;
	int flag,flag_second;
	for(int i=si+1;i<=n;++i){
		if(dis[si][i]<Maxx){
			Maxx=dis[si][i];
			flag=i;
		}
		else
		 if(dis[si][i]==Maxx&&h[i]<h[flag]) flag=i;
	}
	if(id==2){
		if(Ans_A+Ans_B+Maxx>X) return;
		if(Maxx>X) return;
		Ans_B+=Maxx;
		Get_Ans1(flag,1);
	}
	else{
       for(int i=si+1;i<=n;++i){
		if(dis[si][i]<Max_second&&i!=flag){
			  Max_second=dis[si][i];
			  flag_second=i;
		   }
		else
		     if(dis[si][i]==Max_second&&i!=flag&&h[i]<h[flag_second]) flag_second=i;
	     }
	    if(id==1){
           if(Max_second+Ans_A+Ans_B>X) return;
           if(Max_second>X) return;
	       Ans_A+=Max_second;
	       Get_Ans1(flag_second,2);
 	    }
	}

}
void Get_Ans2(int si,int id,int ft){/*1---->A,2----->B*/
	long long Maxx=1000000010;
	long long Max_second=1000000010;
	int flag,flag_second;
	for(int i=si+1;i<=n;++i){
		if(dis[si][i]<Maxx){
			Maxx=dis[si][i];
			flag=i;
		}
		else
		 if(dis[si][i]==Maxx&&h[i]<h[flag]) flag=i;
	}
	if(id==2){
		if(Ans_A+Ans_B+Maxx>ft) return;
		if(Maxx>ft) return;
		Ans_B+=Maxx;
		Get_Ans2(flag,1,ft);
	}
	else{
       for(int i=si+1;i<=n;++i){
		if(dis[si][i]<Max_second&&i!=flag){
			  Max_second=dis[si][i];
			  flag_second=i;
		   }
		else
		     if(dis[si][i]==Max_second&&i!=flag&&h[i]<h[flag_second]) flag_second=i;
	     }
	    if(id==1){
           if(Max_second+Ans_A+Ans_B>ft) return;
           if(Max_second>ft) return;
	       Ans_A+=Max_second;
	       Get_Ans2(flag_second,2,ft);
 	    }
	}

}
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]);
	for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) dis[i][j]=abs(h[i]-h[j]);
	scanf("%d",&X);
	scanf("%d",&Q);
	for(int i=1;i<=Q;++i) scanf("%d%d",&s[i],&x[i]);
	for(int i=1;i<=n;++i){
		Ans_A=Ans_B=0;
		Get_Ans1(i,1);
		if(Ans_B==0){
			if(Ans>1000000010){
				Ans=1000001000;
				flag=i;
			}
			else
			 if(Ans==1000000010&&h[i]>h[flag]) flag=i;
		}
		else
		 if(Ans>(double)Ans_A/Ans_B){
            Ans=(double)Ans_A/Ans_B;
            flag=i;
		 }
		 else
		  if(Ans==(double)Ans_A/Ans_B&&h[i]>h[flag]) flag=i;
	 //printf("%d %d\n",Ans_A,Ans_B);
	}
	printf("%d\n",flag);
	for(int i=1;i<=Q;++i){
		Ans_A=Ans_B=0;
		Get_Ans2(s[i],1,x[i]);
		printf("%d %d\n",Ans_A,Ans_B);
	}
}
/*
5
-1000000000 0 -999999999 999999999 1000000000
1000000000
7
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
1 2
2 3
*/