洛谷 P1081 开车旅行（70）

题目描述

小 $ii的海拔高度为H_iHi，城市 ii和城市jj之间的距离 d_[i,j]d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d_[i,j]=|H_i-H_j|d[i,j]=∣Hi−Hj∣。$

旅行过程中，小

在启程之前，小

对于一个给定的 $X=X_0X=X0，从哪一个城市出发，小AA 开车行驶的路程总数与小BB 行驶的路程总数的比值最小（如果小 BB 的行驶路程为00，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小AA 开车行驶的路程总数与小 BB行驶的路程总数的比值都最小，则输出海拔最高的那个城市。$
对任意给定的 $X=X_iX=Xi和出发城市S_iSi，小 AA 开车行驶的路程总数以及小 BB行驶的路程总数。$

输入输出格式

输入格式：

第一行包含一个整数

第二行有 $H_1,H_2,…,H_nH1,H2,…,Hn，且每个 H_iHi都是不同的。$

第三行包含一个整数 $X_0X0。$

第四行为一个整数 $S_iSi和X_iXi。$

接下来的 $S_iSi和 X_iXi，表示从城市S_iSi出发，最多行驶 X_iXi公里。$

输出格式：

输出共

第一行包含一个整数 $S_0S0，表示对于给定的 X_0X0，从编号为 S_0S0 的城市出发，小 AA开车行驶的路程总数与小BB 行驶的路程总数的比值最小。$

接下来的 $S_iSi和X_iXi下小 AA 行驶的里程总数和小 BB 行驶的里程总数。$

输入输出样例

输入样例#1：复制

输出样例#1：复制

输入样例#2：复制

10 
4 5 6 1 2 3 7 8 9 10 
7 
10 
1 7 
2 7 
3 7 
4 7 
5 7 
6 7 
7 7 
8 7 
9 7 
10 7

输出样例#2：复制

说明

【输入输出样例1说明】

各个城市的海拔高度以及两个城市间的距离如上图所示。

如果从城市

【输入输出样例2说明】

当

如果从城市

从城市

【数据范围与约定】

对于30%的数据，有 $-10^9≤H_i≤10^9−109≤Hi≤109, 0≤X_0≤10^90≤X0≤109, 1≤S_i≤N,0≤X-i≤10^91≤Si≤N,0≤X−i≤109，数据保证H_iHi互不相同。$

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100010
using namespace std;
int n,m,ans;
long long x0;
long long map[MAXN][3][3];
long long h[MAXN],dis[MAXN];
struct nond{ int id;long long dis,H; }v[MAXN];
bool cmp(nond a,nond b){
    if(a.dis==b.dis)    return a.H<b.H;
    return a.dis<b.dis;
}
void pre(){
    memset(map,-1,sizeof(map));
    for(int i=1;i<=n;i++){
        int tot=0;
        for(int j=i+1;j<=n;j++){
            tot+=1;
            v[tot].id=j;v[tot].H=h[j];
            v[tot].dis=abs(h[i]-h[j]);
        }
        sort(v+1,v+1+tot,cmp);
        map[i][1][1]=v[1].dis;map[i][2][1]=v[2].dis;
        map[i][1][2]=v[1].id;map[i][2][2]=v[2].id;
        memset(v,-1,sizeof(v));
    }
}
void work1(){
    double minn=1e9+7,hh=-1,flag=0;
    for(int i=1;i<=n;i++){
        long long peo=0,pos=i,sa=0,sb=0;
        while(1){
            peo%=2;
            if(peo==0){
                if(map[pos][2][1]+sa+sb>x0||map[pos][2][1]==-1)    break;
                peo+=1;sa+=map[pos][2][1];
                pos=map[pos][2][2];flag=1;
            }
            else if(peo==1){
                if(map[pos][1][1]+sa+sb>x0||map[pos][1][1]==-1)    break;
                peo+=1;sb+=map[pos][1][1];
                pos=map[pos][1][2];flag=1;
            }
        }
        if(sb==0)    continue;
        double tmp=(sa*1.0)/(sb*1.0);
        if(tmp<minn){ minn=tmp;ans=i;hh=h[i]; }
        else if(tmp==minn&&h[i]>hh)    ans=i,hh=h[i];
    }
    if(minn==1e9+7&&flag==1){
        minn=0;
        for(int i=1;i<=n;i++)
            if(h[i]>minn){
                minn=h[i];
                ans=i;
            }
    }
    cout<<ans<<endl;
}
void work2(int pos,int x){
    long long sa=0,sb=0,peo=0;
    while(1){
        peo%=2;
        if(peo==0){
            if(map[pos][2][1]+sa+sb>x||map[pos][2][1]==-1)    break;
            peo+=1;sa+=map[pos][2][1];
            pos=map[pos][2][2];
        }
        else if(peo==1){
            if(map[pos][1][1]+sa+sb>x||map[pos][1][1]==-1)    break;
            peo+=1;sb+=map[pos][1][1];
            pos=map[pos][1][2];
        }
    }
    cout<<sa<<" "<<sb<<endl; 
}
int main(){
    freopen("drive.in","r",stdin);
    freopen("drive.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&h[i]);
    scanf("%lld",&x0);
    pre();
    work1();
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        long long s,x;
        scanf("%lld%lld",&s,&x);
        work2(s,x);
    }
}
/*
5
-1000000000 0 -999999999 999999999 1000000000
1000000000
7
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
1 2
2 3
*/

70分暴力