记录编号	469924	评测结果	AWWWWWWWWWTTTTTTTTTT
题目名称	[NOIP 2012]开车旅行	最终得分	5
用户昵称	lingyixiaoyao	是否通过	未通过
代码语言	C++	运行时间	20.767 s
提交时间	2017-11-03 22:01:26	内存使用	23.20 MiB

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <climits>
using namespace std;
const int maxn=1000000+10;

int n,m;
int min1,min2;
struct node
{
    int h,id;
}a[maxn];
int next1[maxn],next2[maxn],cnt,tt,l,r;
int dis1[maxn];
int dis2[maxn];
double ans=1.0*INT_MAX/2,ans1;

int getint();
void dfs(int i,int x,int sum1,int sum2,int p);

int main()
{
	freopen("drive.in","r",stdin);
	freopen("drive.out","w",stdout);
	
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        a[i].h=getint();
    }
    for(int i=1;i<=n;i++)
    {
        min1=INT_MAX/2,min2=INT_MAX/2;
        for(int j=i+1;j<=n;j++)
        {
            if(abs(a[i].h-a[j].h)<min1)
            {
                min2=min1;
                next1[i]=next2[i];
                min1=abs(a[i].h-a[j].h);
                next2[i]=j;
            }
            else if(abs(a[i].h-a[j].h)<min2 && abs(a[i].h-a[j].h)!=min1)
            {
                min2=abs(a[i].h-a[j].h);
                next1[i]=j;
            }
            else if(abs(a[i].h-a[j].h) == min1 && a[j].h>a[next2[i]].h)
            {
                min2=min1;
                next1[i]=j;
            }
            else if(abs(a[i].h-a[j].h) == min1 && a[j].h<a[next2[i]].h)
            {
                min2=min1;
                next1[i]=next2[i];
                next2[i]=j;
            }

        }
    }
    scanf("%d",&tt);
   
    for(int i=1;i<=n;i++)
    {
        dfs(i,i,0,0,1);
        if(dis2[i]==0) ans1=1.0*INT_MAX;
        else ans1=1.0*dis1[i]/dis2[i];
        if(ans1<ans)
        {
            ans=ans1;
            cnt=i;
        }
    } 
    cout<<cnt<<endl;
    memset(dis1,0,sizeof(dis1));
    memset(dis2,0,sizeof(dis2));

    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        memset(dis1,0,sizeof(dis1));
        memset(dis2,0,sizeof(dis2));
        dfs(l,l,0,0,1);
        printf("%d %d\n",dis1[l],dis2[l]);    
    }
}
void dfs(int i,int x,int sum1,int sum2,int p)
{
    if(p==1)
    {
        if(sum1+sum2+abs(a[x].h-a[next1[x]].h)>tt || next1[x] == 0)
        {
            dis1[i]=sum1;
            dis2[i]=sum2;
            return ;
        }
        sum1+=abs(a[x].h-a[next1[x]].h);
        dfs(i,next1[x],sum1,sum2,2);
    }
    else
    {
        if(sum1+sum2+abs(a[x].h-a[next2[x]].h)>tt || next2[x] == 0)
        {
            dis1[i]=sum1;
            dis2[i]=sum2;
            return ;
        }
        sum2+=abs(a[x].h-a[next2[x]].h);
        dfs(i,next2[x],sum1,sum2,1);
    }
}
int getint()
{
	char ch;
	int s=1,x=0;
	while(ch=getchar(),ch>'9' || ch<'0')
	{
		if(ch=='-')
			s=-1;
	}
	while(ch>='0' && ch<='9')
	{
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return s*x;
}