记录编号	315972	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]开车旅行	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	3.733 s
提交时间	2016-10-06 07:46:42	内存使用	50.25 MiB

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <cstring>
using namespace std;
#define E puts("")
const int maxn = 110000;
typedef long long LL;
const double INF = 5000000000LL;
const double eps = 1e-10;
int dcmp(double x){
	if(fabs(x) < eps) return 0;
	return x < 0 ? -1 : 1;	
}
int n,m;
struct City
{
	int num,h;	
	bool operator < (const City &b)const
	{
		return h < b.h;	
	}
}c[maxn];
set < City > q;
set < City > :: iterator it;
#define read(x) scanf("%d",&x)
void Read_one(){
	read(n);
	for(int i=1;i<=n;i++){	
		read(c[i].h); c[i].num = i;	
	}
}
struct Temp // 暂时存储i城市的next 
{
	int num,dif;
	bool operator < (const Temp &b)const
	{
		if(dif != b.dif) return dif < b.dif;
		return c[num].h < c[b.num].h;	
	}
}t[5]; 
int nexta[maxn],nextb[maxn];
void Find_next(int i){
	it = q.find(c[i]);
	int _t = 0;
	if(it != q.begin()){
		it -- ;
		t[++_t] = (Temp){ (*it).num , abs((*it).h - c[i].h) };
		if(it != q.begin()){
			it -- ;
			t[++_t] = (Temp){ (*it).num , abs((*it).h - c[i].h) };	
			it ++ ;
		}
		it ++ ;
	}
	if((++it) != q.end()){
		t[++_t] = (Temp){ (*it).num , abs((*it).h - c[i].h) };
		if((++it) != q.end()){
			t[++_t] = (Temp){ (*it).num , abs((*it).h - c[i].h) };
		}
	}
	sort(t + 1,t + 1 + _t);
	nextb[i] = t[1].num; if(_t == 1) return;
	nexta[i] = t[2].num;
}
void Prepare_next(){
	for(int i=n;i>0;i--){
		q.insert(c[i]);
		if(i != n) Find_next(i);
	}	
	/*
	puts("next : ");
	for(int i=1;i<=n;i++){
		printf("A = %d  B = %d\n",nexta[i],nextb[i]);	
	}E;
	*/
}
LL fa[maxn][23],fb[maxn][23];
int f[maxn][23];
void Prepare_f(){
	for(int i=1;i<=n;i++){
		int pos1 = nexta[i], pos2 = nextb[nexta[i]];
		//从i出发走1轮
		fa[i][0] = pos1 ? abs(c[pos1].h - c[i].h) : 0;
		fb[i][0] = pos2 ? abs(c[pos2].h - c[pos1].h) : 0;
		f[i][0] = pos2; // 最后停在pos2	
	}
	for(int j=1;j<20;j++){
		for(int i=1;i<=n;i++){
			f[i][j] = f[f[i][j-1]][j-1];
			fa[i][j] = fa[i][j-1] + fa[f[i][j-1]][j-1];
			fb[i][j] = fb[i][j-1] + fb[f[i][j-1]][j-1];
		} 
	}
}
int x0,ans=0;
LL da = 0 , db = 0;
 
double Query(int St,int X){
//	printf("S = %d  : ",St);
	da = 0; db = 0;
	for(int i=20;i>=0;i--){
		if(f[St][i] && fa[St][i] + fb[St][i] <= X){
			da += (LL)fa[St][i];  db += (LL)fb[St][i];
			X -= fa[St][i] + fb[St][i];
			St = f[St][i];
		}	
	}
	int posa=nexta[St];
	if(posa){
		LL dis = abs(c[posa].h - c[St].h);
		if(dis <= X) da += dis;
	}
	if(!db) return INF;
	else return ((long double)da/(long double)db);
}
void calc_one(){
	cin >> x0; ans = 0;
	double Min = 1e100;
	for(int i=1;i<=n;i++){
		double temp = Query(i,x0);
		if(dcmp(Min - temp) > 0 || (!dcmp(Min - temp) && c[ans].h < c[i].h)){
			Min = temp ; ans = i;
		}
	}
	printf("%d\n",ans);
}
void calc_two(){
	cin >> m;
	while(m -- ){
		int si,xi; cin >> si >> xi;
		double temp = Query(si,xi);
		printf("%lld %lld\n",da,db);
	}
}
void lala();
int main(){
	freopen("drive.in","r",stdin);freopen("drive.out","w",stdout);
	Read_one();
	Prepare_next();
	Prepare_f();
	calc_one();
	calc_two();
	return 0;
	//lala();
	for(;;);
}
void lala(){
	double X,Y;
	while(scanf("%lf%lf",&X,&Y)==2){
		printf("%d\n",dcmp(X - Y));	
	}
}
 
/*
5
-1000000000 0 -999999999 999999999 1000000000
1000000000
7
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
1 2
2 3
 
2
 
*/