Description
小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 行驶的路程总数。
Input
第一行包含一个整数 N，表示城市的数目。
第二行有 N 个整数，每两个整数之间用一个空格隔开，依次表示城市 1 到城市 N 的海拔高度，即 H1，H2，……，Hn，且每个 Hi 都是不同的。
第三行包含一个整数 X0。
第四行为一个整数 M，表示给定 M 组 Si 和 Xi。
接下来的 M 行，每行包含 2 个整数 Si 和 Xi，表示从城市 Si 出发，最多行驶 Xi 公里。
Output
输出共 M+1 行。
第一行包含一个整数 S0，表示对于给定的 X0，从编号为 S0 的城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。
接下来的 M 行，每行包含 2 个整数，之间用一个空格隔开，依次表示在给定的 Si 和Xi 下小 A 行驶的里程总数和小 B 行驶的里程总数。
Sample Input&&Hint
【样例输入1】
4
2 3 1 4
3
4
1 3
2 3
3 3
4 3
【样例输入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
【样例输出1】
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出发，可以到达的城市为3,4，这两个城市与城市2的距离分别为2,1，由于城市3离城市2第二近，所以小A会走到城市3。到达城市3后，前面尚未旅行的城市为4，所以城市4离城市3最近，但是如果要到达城市4，则总路程为2+3=5>3，所以小 B会直接在城市3结束旅行。
如果从城市3出发，可以到达的城市为4，由于没有离城市3第二近的城市，因此旅行还未开始就结束了。
如果从城市4出发，没有可以到达的城市，因此旅行还未开始就结束了。 【样例输出2】 2 3 2 2 4 2 1 2 4 5 1 5 1 2 1 2 0 0 0 0 0 【输入输出样例2说明】 当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；
对于 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互不相同。
Part 1 预处理
首先要处理出小A和小B怎么走。 我们用ga（i）、gb（i)分别表示小A、小B行驶到的下一个城市 容易想到，嗯，
法一：暴力求解 枚举1-n的每一个城市，对于每个城市i，从（i+1-n）中选取距离最小的两个城市。时间复杂度 n^2.爆啦！surprise mother f**ker
接下来讲讲正解，有个神奇的东西叫做#inclue<set>
它支持logn级别的插入和查询，并对内部的数进行排序
s.insert(x);//插入x
s.lower_bound(x);//查找**大于等于**x的最小元素，返回迭代器
s.upper_bound(x);//查找**大于**x的最小元素，返回迭代器
所以。对于当前城市i
最近的和第二近的只会在
四个位置出现 PS：这里有个细节，他们只能向编号更大的城市走去，所以可以用个小技巧，倒着处理**。
for(int i=n; i>=1; i--)
q.insert(h[i]);
Part 2 动态规划
– 本题关键
- 在哪里（城市）
- 开了多久（天数）
- A、B行驶的长度
但其实知道前两个就可以推出第三个。
因此我们可以定义
f[i,j,k]表示从城市j出发，两人一共行驶i天，k先开车最终会到达的城市。其中k=0表示A开车，k=1表示B开车。
但是优秀的实现复杂度又爆炸了
于是终极大魔王出现了！
倍增DP
我们将i改为一共行驶了2^i天。
于是初值：
f[0,j,0]=ga(j),f[0,j,1]=gb(j)
当i=1时，因为2^0是奇数，所以两人从j出发开2^1天所到达的城市，等于k先开2^0天，另一人再开2^0天所到达的城市
f[1,j,k]=f[0,f[0,j,k]，1-k/*换了个人开*/]
当i>1时，你怎么折腾2^i都是偶数，所以不会换人，而两人从j出发开2^i天所到达的城市，等于等于k先开2^i-1天，k再开2^i-1天所到达的城市。
所以
f[i,j,k]=f[i-1,f[i-1,j,k],k]
**这里有个小问题，需要注意超出n的边界的情况，所以需要特判
鉴于f数组，于是易得
定义da[i,j,k]表示从j城出发，由k先开，行驶2^i天，小A走的路程
当i==1时da[1,j,k]=da[0,j,k]+da[0,f[0,j,k],i-k];
否则 da[i,j,k]=da[i-1,j,k]+da[i-1,f[0,j,k],1-k];
我们定义db[i,j,k]表示从j城出发，由k先开，行驶2^i天,小B走的路程
当i==1时db[1,j,k]=db[0,j,k]+db[0,f[0,j,k],i-k];
否则 db[i,j,k]=db[i-1,j,k]+db[i-1,f[0,j,k],1-k];
时间复杂度Nlog N. 但是这里仅算出了2^i次方下的情况。于是我们需要满足求出从城市S出发最多行驶X公里时，A和B走了多远。
我们按倒叙枚举2的i次方，基于二进制划分的思想来拼凑X。
1.倒叙循环i=logN-0
2.对于每个i若两人从p出发行驶2^i天累计路程仍未超过x，则令累计路程加上x，并行驶到该城市
3.循环结束后即为所求。
最终实现了logN查询的复杂度。
然后对于问题。。。瞎折腾呗反正logN！
[问题1]枚举！然后计算取比值最小的即为答案 [问题2]多次计算。
于是整个算法的时间复杂度O((N+M)log N)
代码来了
马蜂太丑不敢看
#include<iostream>
#include<set>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std;
//最大坑点！本题要开long long
const long long INF=0x7fffffffffffffff/2;
double ans=10000000000;
struct node
{
long long h;
int id;
} h[100005],ga[100005],gb[100005];//储存城市信息
struct point
{
long long la,lb;
};
bool operator <(node as,node bs)
{
if(as.h!=bs.h)return as.h<bs.h;
else return as.id<bs.id;
}//重载运算符
set<node> q;//以城市为单位入set
int n,f[20][100005][3];
long long da[20][100005][3],db[20][100005][3];
bool cmp(node as,node bs)
{
return as.h<bs.h;
}
point Calc(int p,int x)//计算以p为起点，行驶距离不超过x的路程和
{
long long la=0,lb=0;
for(int i=18; i>=0; i--)//倒叙
{
if(f[i][p][0]&&la+lb+da[i][p][0]+db[i][p][0]<=x)
{
la+=da[i][p][0];
lb+=db[i][p][0];
p=f[i][p][0];
}
}
return {la,lb};
}
int main()
{
scanf("%d",&n);
q.insert({INF,0});
q.insert({INF-1,0});
q.insert({-INF,0});
q.insert({-INF+1,0});//边界处理，预防预处理时越界
for(int i=1; i<=n; i++)
{
scanf("%lld",&h[i].h);
h[i].id=i;
}
for(int i=n; i>=1; i--)//倒叙
{
q.insert(h[i]);
node t[5];
t[1]=*--q.lower_bound(h[i]);
t[2]=*--q.lower_bound(t[1]);
t[3]=*q.upper_bound(h[i]);
t[4]=*q.upper_bound(t[3]);//查找4个可能为最近城市
for(int j=1; j<=4; j++)t[j].h=abs(t[j].h-h[i].h);
sort(t+1,t+5,cmp);//排序
ga[i]=t[2];
gb[i]=t[1];
}
for(int i=1; i<n; i++)
{
f[0][i][0]=ga[i].id;
f[0][i][1]=gb[i].id;
}
for(int i=1; i<=18; i++)
for(int j=1; j<=n; j++)
if(j+(1<<i)<=n)//预防越界
for(int k=0; k<=1; k++)
{
if(i==1)f[1][j][k]=f[0][f[0][j][k]][1-k];
else f[i][j][k]=f[i-1][f[i-1][j][k]][k];
}
memset(da,127/3,sizeof(da));
memset(db,127/3,sizeof(db));//当不可到达时默认为最大
for(int i=1; i<=n; i++)
{
da[0][i][0]=ga[i].h;
da[0][i][1]=0;
}
for(int i=1; i<=18; i++)
for(int j=1; j<=n; j++)
if(j+(1<<i)<=n)//预防越界
for(int k=0; k<=1; k++)
{
if(i==1)
{
da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k];
}
else da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k];
}
for(int i=1; i<=n; i++)
{
db[0][i][0]=0;
db[0][i][1]=gb[i].h;
}
for(int i=1; i<=18; i++)
for(int j=1; j<=n; j++)
if(j+(1<<i)<=n)//预防越界
for(int k=0; k<=1; k++)
{
if(i==1)
{
db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][k^1];
}
else db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][k];
}
int x0,m;
scanf("%d",&x0);
int ddd=0;
for(int i=1; i<=n; i++)//枚举找出最小比
{
point tmp=Calc(i,x0);
if(tmp.lb==0)continue;//防止除0
double ccf=(long double)tmp.la/(long double)tmp.lb;
if(ccf<ans)ans=ccf,ddd=i;
}
printf("%d\n",ddd);
scanf("%d",&m);
for(int i=1; i<=m; i++)
{
int si,xi;
scanf("%d%d",&si,&xi);
point tmp=Calc(si,xi);//依次计算
printf("%lld %lld\n",tmp.la,tmp.lb);
}
}
飛べる魚 