链接：https://ac.nowcoder.com/acm/problem/16562
来源：牛客网
题目描述
小 A 和小 B 决定利用假期外出旅行，他们将想去的城市从 1 到 N 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i 的海拔高度为 Hi ，城市 i 和城市 j 之间的距离 d[i,j] 恰好是这两个城市海拔高度之差的绝对值，即 d[i,j]=|Hi-Hj|旅行过程中，小 A 和小 B 轮流开车，第一天小 A 开车，之后每天轮换一次。他们计划选择一个城市 S 作为起点，一直向东行驶，并且最多行驶 X 公里就结束旅行。小 A 和小 B 的驾驶风格不同，小 B 总是沿着前进方向选择一个最近的城市作为目的地，而小 A 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 X 公里，他们就会结束旅行。
在启程之前，小 A 想知道两个问题： 1.对于一个给定的 X=X0 ，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 0 ，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
2.对任意给定的 X=Xi 和出发城市 Si ，小 A 开车行驶的路程总数以及小 B 行驶的路程总数。
输入描述:
第一行包含一个整数 N ，表示城市的数目。1
第二行有 N 个整数，每两个整数之间用一个空格隔开，依次表示城市 1 到城市 N 的海拔高度，即 H
,H2
,…,Hn
，且每个 Hi
都是不同的。0
第三行包含一个整数 X
。i
第四行为一个整数 M ，表示给定 M 组 S
和 Xi
。i
接下来的 M 行，每行包含 2 个整数 S
和 Xi
，表示从城市 Si
出发，最多行驶 Xi
公里。
输出描述:
输出共 M+1 行。0
第一行包含一个整数 S
，表示对于给定的 X0
，从编号为 S0
的城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。i
接下来的 M 行，每行包含 2 个整数，之间用一个空格隔开，依次表示在给定的 S
和 Xi
下小 A 行驶的里程总数和小 B 行驶的里程总数。示例1
输入
复制4 2 3 1 4 3 4 1 3 2 3 3 3 4 3
输出
复制1 1 1 2 0 0 0 0 0
说明
各个城市的海拔高度以及两个城市间的距离如上图所示。
如果从城市 1 出发，可以到达的城市为 2,3,4 ，这几个城市与城市 1 的距离分别为 1,1,2 ，但是由于城市 3 的海拔高度低于城市 2 ，所以我们认为城市 3 离城市 1 最近，城市 2 离城市 1 第二近，所以小A会走到城市 2 。到达城市 2 后，前面可以到达的城市为 3,4 ，这两个城市与城市 2 的距离分别为 2,1 ，所以城市 4 离城市 2 最近，因此小B会走到城市 4 。到达城市 4 后，前面已没有可到达的城市，所以旅行结束。示例2
如果从城市 2 出发，可以到达的城市为 3,4 ，这两个城市与城市 2 的距离分别为 2,1 ，由于城市 3 离城市 2 第二近，所以小A会走到城市 3 。到达城市 3 后，前面尚未旅行的城市为 4 ，所以城市 4 离城市 3 最近，但是如果要到达城市 4 ，则总路程为 2+3=5>3 ，所以小B会直接在城市 3 结束旅行。
如果从城市 3 出发，可以到达的城市为 4 ，由于没有离城市 3 第二近的城市，因此旅行还未开始就结束了。
输入
复制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 3 2 2 4 2 1 2 4 5 1 5 1 2 1 2 0 0 0 0 0
说明
当 X=7 时，如果从城市 1 出发，则路线为 1 → 2 → 3 → 8 → 9 ，小A走的距离为 1+2=3 ，小B走的距离为 1+1=2 。（在城市 1 时，距离小A最近的城市是 2 和 6 ，但是城市 2 的海拔更高，视为与城市 1 第二近的城市，所以小A最终选择城市 2 ；走到 9 后，小A只有城市 10 可以走，没有第 2 选择可以选，所以没法做出选择，结束旅行）
如果从城市 2 出发，则路线为 2 → 6 → 7 ，小A和小B走的距离分别为 2,4 。
如果从城市 3 出发，则路线为 3 → 8 → 9 ，小A和小B走的距离分别为 2,1 。
如果从城市 4 出发，则路线为 4 → 6 → 7 ，小A和小B走的距离分别为 2,4 。
如果从城市 5 出发，则路线为 5 → 7 → 8 ，小A和小B走的距离分别为 5,1 。
如果从城市 6 出发，则路线为 6 → 8 → 9 ，小A和小B走的距离分别为 5,1 。
如果从城市 7 出发，则路线为 7 → 9 → 10 ，小A和小B走的距离分别为 2,1 。
如果从城市 8 出发，则路线为 8 → 10 ，小A和小B走的距离分别为 2,0 。
如果从城市 9 出发，则路线为 9 ，小A和小B走的距离分别为 0,0 （旅行一开始就结束了）。
如果从城市 10 出发，则路线为 10 ，小A和小B走的距离分别为 0,0 。
从城市 2 或者城市 4 出发小A行驶的路程总数与小B行驶的路程总数的比值都最小，但是城市 2 的海拔更高，所以输出第一行为 2 。
备注:
对于30%的数据，有 1≤N≤20,1≤M≤20 ；9
对于40%的数据，有 1≤N≤100,1≤M≤100 ；
对于50%的数据，有 1≤N≤100,1≤M≤1,000 ；
对于70%的数据，有 1≤N≤1,000,1≤M≤10,000 ；
对于100%的数据，有 1≤N≤100,000,1≤M≤100,000 , -10
≤Hi
≤109
,0≤X0
≤109
, 1≤Si
≤N,0≤X-i≤109
，数据保证 Hi
互不相同。
分析：
有特定的两种路线，类似于cf932，后面的节点必须比前面的结点的权值大，所以可以维护两个倍增数组
设da[i][j][k] 表示每次走第二近的点 从 第 i 个点以 k 的方式开始 走 2^j 次天，走过的最远距离
db[i][j][k] 表示每次走最近的点 从 第 i 个点在 第 2^j’ 次 天以 k 的方式开始 走 2^j 次天，走过的最远距离
然后将每个点放入计算 走 x0 的距离所能走的最大比值，算出位置即可
其它点也一样
//#define int ll
const int N = 1e5+10;
int n,m,x0;
int h[N],s[N],x[N];
int la,lb,ansid;
double ans = INF * 1.0;
struct city {
int id,h;
friend bool operator<(const city &a,const city &b) {
return a.h < b.h;
}
};
multiset<city> q;
int f[N][20][2],da[N][20][5],db[N][20][5];
void init() {
h[0] = INF,h[n+1] = -INF;
city st;
st.id = 0,st.h = INF;
q.insert(st),q.insert(st);
st.id = n + 1,st.h = -INF;
q.insert(st);
q.insert(st);
of(i,n,1) {
int ga,gb;
city now;
now.id = i,now.h = h[i];
q.insert(now);
set<city>::iterator p = q.lower_bound(now);
p -- ;
int lt = (*p).id,lh = (*p).h;//比它小但最近的点
p ++ ,p ++ ;
int ne = (*p).id,nh = (*p).h;//比它大但最近的点
p -- ;
if(abs(nh - h[i]) >= abs(h[i] - lh)) {//海拔低的点更近
gb = lt;
p -- ,p -- ;
if(abs(nh - h[i]) >= abs(h[i] - (*p).h)) {
ga = (*p).id;
} else {
ga = ne;
}
} else {
gb = ne;
p ++,p ++ ;
if(abs((*p).h - h[i]) >= abs(h[i] - lh)) {
ga = lt;//第二大的
} else {
ga = (*p).id;
}
}
f[i][0][0] = ga,f[i][0][1] = gb;
da[i][0][0] = abs(h[i] - h[ga]);
db[i][0][1] = abs(h[i] - h[gb]);
}
fo(j,1,18) {
fo(i,1,n) {
fo(k,0,1) {
if(j ==1) {
f[i][j][k] = f[f[i][j-1][k]][j-1][1-k];
da[i][j][k] = da[i][j-1][k] + da[f[i][j-1][k]][j-1][1-k];
db[i][j][k] = db[i][j-1][k] + db[f[i][j-1][k]][j-1][1-k];
} else {
f[i][j][k] = f[f[i][j-1][k]][j-1][k];
da[i][j][k] = da[i][j-1][k] + da[f[i][j-1][k]][j-1][k];
db[i][j][k] = db[i][j-1][k] + db[f[i][j-1][k]][j-1][k];
}
}
}
}
}
void calc(int s,int x) {
int t = s;
la = 0,lb = 0;
of(j,18,0) {
if(f[t][j][0] && la + lb + da[t][j][0] + db[t][j][0] <= x) {
la += da[t][j][0];
lb += db[t][j][0];
t = f[t][j][0];
}
}
}
void solve()
{
cin>>n;
fo(i,1,n) {
cin>>h[i];
}
cin>>x0>>m;
fo(i,1,m) {
cin>>s[i]>>x[i];
}
init();
fo(i,1,n) {
calc(i,x0);
double nowans = (double) la / (double) lb;
if(nowans < ans) {
ans = nowans;
ansid = i;
}
else if( nowans == ans && h[ansid] < h[i]) ansid = i;
}
cout<<ansid<<endl;
fo(i,1,n) {
fo(j,0,18)
cout<<da[i][j][1]<<' ';
cout<<endl;
} cout<<endl;
for(int i = 1;i<= m; i ++ ) {
calc(s[i],x[i]);
cout<<la<<' '<<lb<<endl;
}
}
标签：10,set,NOIP2012,int,城市,距离,行驶,倍增,出发 From： https://www.cnblogs.com/er007/p/16659691.html