版权yangyaojia.cnblogs.com
1.给出x0，求从哪一个城市出发，使得A走的路程/B走的路程最小。如果B走的路程=0，则比值视为无穷大。如果有多个城市满足要求，则输出海拔最高的那个城市。
2.给出x和s（出发城市），求旅行终止是A的路程和B的路程。
第一行包含一个整数 N，表示城市的数目。
第二行有 N 个整数，每两个整数之间用一个空格隔开，依次表示城市 1 到城市 N 的海拔高度，即H1，H2，……，Hn，且每个Hi都是不同的。
第三行包含一个整数 X0。
第四行为一个整数 M，表示给定M组Si和 Xi。
接下来的M行，每行包含2个整数Si和Xi，表示从城市 Si出发，最多行驶Xi公里。
输出共M+1 行。
第一行包含一个整数S0，表示对于给定的X0，从编号为S0的城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值最小。
接下来的 M 行，每行包含 2 个整数，之间用一个空格隔开，依次表示在给定的 Si和Xi下小A行驶的里程总数和小B 行驶的里程总数。
4 2 3 1 4 3 4 1 3 2 3 3 3 4 3
【数据范围】
对于 30%的数据，有 1≤N≤20，1≤M≤20；
对于 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≤10,000，-1,000,000,000≤Hi≤1,000,000,000，
0≤X0≤1,000,000,000，1≤Si≤N，0≤Xi≤1,000,000,000，数据保证 Hi互不相同。
解题方案
这一道题翻了题解才做出来，我在这里总结一下。
我们很容易可以发现，这可以用线段上的倍增来跳点。
我们可以把A和B合成一轮，这样我们用f[i][j]带表从第i个点跳2j轮所到达的点。
用da[i][j]代表第i个点跳2j轮所到达的点时A所走的路程。db[i][j]也是同样的意义。
所以计算路程的方法与倍增跳点的方法一样。关键是怎么出预处理，求出da[i][0],db[i][0],与f[i][0]
其实，网上有很多介绍预处理的实现方法，但主要的思想都是这样的：
我们可以从n到1依次将点（以其高度为关键字，并记下其编号）丢入一个有序队列。那么如果刚加进的点序号为i，最近点与次近点只可能在i-2，i-1,i+1,i+2中。我们就可以在这里确定数组sa[i]，代表i号点的次近点，sb[i]代表i号点最近点。因为加入的顺序为n到1，所以肯定是合理的。
我们可以得到
f[i][0]=sb[sa[i]];
da[i][0]=abs(h[i]-h[sa[i]]);
db[i][0]=abs(h[sa[i]]-h[sb[sa[i]]]);
#include <cstdio> #include <iostream> #include <cmath> #include <queue> #include <algorithm> #include <cstring> #include <climits> #include <set> #define MAXN 100000+10 #define Pair pair<long long,long long> using namespace std; long long n,a[MAXN],sa[MAXN],sb[MAXN],x0,m; long long f[MAXN][20],da[MAXN][20],db[MAXN][20]; long long read(){ long long in=0;char ch=getchar(); for(;ch<‘0‘||ch>‘9‘;ch=getchar()); for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar())in=in*10+ch-‘0‘; return in; } set <Pair> s; set <Pair> :: iterator it1; set <Pair> :: iterator it2; void init() { for(long long i=n;i>=1;i--) { long long num=0; pair<Pair,long long> tmp[5];memset(tmp,0,sizeof(tmp)); s.insert(Pair(a[i],i)); it2=it1=s.find(Pair(a[i],i)); if(it1!=s.begin()) { it1--; tmp[++num].first.first=abs((*it1).first-a[i]); tmp[num].first.second=(*it1).first; tmp[num].second=(*it1).second; if(it1!=s.begin()) { it1--; tmp[++num].first.first=abs((*it1).first-a[i]); tmp[num].first.second=(*it1).first; tmp[num].second=(*it1).second; } } if(it2!=--s.end()) { it2++; tmp[++num].first.first=abs((*it2).first-a[i]); tmp[num].first.second=(*it2).first; tmp[num].second=(*it2).second; if(it2!=--s.end()) { it2++; tmp[++num].first.first=abs((*it2).first-a[i]); tmp[num].first.second=(*it2).first; tmp[num].second=(*it2).second; } } sort(tmp+1,tmp+num+1); sb[i]=tmp[1].second; if(num>=2) sa[i]=tmp[2].second; f[i][0]=sb[sa[i]]; if(sa[i]) da[i][0]=abs(a[i]-a[sa[i]]); if(sb[sa[i]]&&sa[i]) db[i][0]=abs(a[sa[i]]-a[sb[sa[i]]]); } for(long long j=1;(1<<j)<=n;j++) { for(long long i=1;i<=n;i++) if(f[i][j-1]) { da[i][j]=da[i][j-1]+da[f[i][j-1]][j-1]; db[i][j]=db[i][j-1]+db[f[i][j-1]][j-1]; f[i][j]=f[f[i][j-1]][j-1]; } } } long long query(long long x,long long d,long long &xx,long long &yy) { long long ansa=0,ansb=0,a=x; for(int j=(int)log2(n);j>=0;j--) if(f[a][j]&&ansa+ansb+da[a][j]+db[a][j]<=d) { ansa+=da[a][j]; ansb+=db[a][j]; a=f[a][j]; } if(sa[a]&&ansa+ansb+da[a][0]<=d) ansa+=da[a][0]; xx=ansa; yy=ansb; } int main() { scanf("%lld",&n); for(long long i=1;i<=n;i++) scanf("%lld",&a[i]); init(); long long bp=0,xx=0,yy=0; scanf("%lld",&x0); for(long long i=1;i<=n;i++) { long long a=0,b=0; query(i,x0,a,b); if(b) { if(bp==0||xx*b>yy*a) { bp=i; xx=a; yy=b; } } } printf("%lld\n",bp); scanf("%lld",&m); for(long long i=1;i<=m;i++) { long long x=0,y=0,ansa=0,ansb=0; scanf("%lld%lld",&x,&y); query(x,y,ansa,ansb); printf("%lld %lld\n",ansa,ansb); }//*/ return 0; }
原文：http://www.cnblogs.com/yangyaojia/p/6399561.html