双向链表+倍增+模拟。
(70pts):
说白了此题的暴力就是细节较多的模拟题。
我们设离(i)城市最近的点的位置为(B[i])，第二近的位置为(A[i])。设(A)或(B)数组等于(0)的的情况不能接下去走到第二或第一近的位置。
- 处理到底能不能继续向下走，即当前城市下一步无法选择城市时，可以直接设置该城市到0城市(即走不到)的距离为正无穷，这样接下来向下走就肯定超过规定路程。
- 在求第一问比值的时候注意精度问题和无穷大问题。
(100pts):
对70分做法进行优化。用双向链表(O(n))初始化求出(A)数组和(B)数组。
因为有方向这个限制，因此每次从小到大求完A、B数组之后都要删除求完之后的节点。
倍增的时候用4个数组。
(C[i][j]：)表示从i出发，(A，B)都走了(1<<j)步所到达的位置。
(disa[i][j]、b、c)分别表示(A，B)都走了(1<<j)步(a)走过的距离、(b)走过的距离、(c)走过的总距离。
距离的倍增递推式为：
(disa[i][j] = disa[i][j - 1] + disa[C[i][j - 1]][j - 1];)
(disb[i][j] = disb[i][j - 1] + disb[C[i][j - 1]][j - 1];)
(disc[i][j] = disa[i][j] + disb[i][j];)
#include <bits/stdc++.h>
#define N 300101
#define int long long
using namespace std;
int n, m, x0, ans0, data[N], pos[N], b[N], a[N];
int C[N][20], disa[N][20], disb[N][20], disc[N][20];
//C是a,b都走了1<<j步所到达的位置，disa是a走了1<<j步所行驶的距离。
struct dat {
int id, h, l, r;//l, r都是当前数组里的值
}da[N];
int d(int x, int i)
{
if (x <= 0 || x > n || i <= 0 || i > n) return 21474836400000007;
return abs(data[x] - data[i]);
}
int d_new(int x, int i)
{
if (da[x].id <= 0 || da[x].id > n || da[i].id <= 0 || da[i].id > n) return 2147483640000007;
return abs(da[x].h - da[i].h);
}
bool cmp(dat a, dat b)
{
return a.h < b.h;
}
inline void isrt(int i, int j)
{
int minn = d_new(pos[i], pos[b[i]]);
int minn2 = d_new(pos[i], pos[a[i]]);
int ha = d_new(pos[i], j);
if (ha < minn || (ha == minn && data[da[j].id] < data[b[i]]) )
{
a[i] = b[i];
b[i] = da[j].id;
}
else if (ha < minn2 || (ha == minn2 && data[da[j].id] < data[a[i]]) )
a[i] = da[j].id;
}
inline void init()
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
da[i].id = i, scanf("%lld", &da[i].h), data[i] = da[i].h;
sort(da + 1, da + 1 + n, cmp);
for (int i = 1; i <= n; i++)
{
pos[da[i].id] = i;
if (i != 1)
da[i].l = i - 1;
if (i != n)
da[i].r = i + 1; //最小值，次小值，一定在这四个位置中各选择一个数。
}
// pos[i]为当前结构体中的位置
for (int i = 1; i <= n; i++)
{
int now = pos[i];
int l_1, l_2, r_1, r_2;
l_1 = da[now].l;
l_2 = da[l_1].l;
r_1 = da[now].r;
r_2 = da[r_1].r;
//更新i点的最近点和第二近点
isrt(i, l_1);
isrt(i, l_2);
isrt(i, r_1);
isrt(i, r_2);
//删除了i这个点
if (da[pos[i]].l)
da[da[pos[i]].l].r = da[pos[i]].r;
if (da[pos[i]].r)
da[da[pos[i]].r].l = da[pos[i]].l;
}
for (int i = 1; i <= n; i++)
{
disa[i][0] = d(a[i], i);
disb[i][0] = d(a[i], b[a[i]]);
disc[i][0] = disa[i][0] + disb[i][0];
C[i][0] = b[a[i]];//c走一次。说明a先走一次，b再走一次。
}
for (int j = 1; j <= 19; j++)
for (int i = 1; i <= n; i++)
{
C[i][j] = C[C[i][j - 1]][j - 1];
if (C[i][j])//如果该位置还能继续走
{
disa[i][j] = disa[i][j - 1] + disa[C[i][j - 1]][j - 1];
disb[i][j] = disb[i][j - 1] + disb[C[i][j - 1]][j - 1];
disc[i][j] = disa[i][j] + disb[i][j];
}
}
}
void s1()
{
int x0, mink = 0;
long double minn = 2147483648787887.0000000000;
scanf("%lld%lld", &x0, &m);
for (int o = 1; o <= n; o++)
{
int x = x0, s = o, ansa = 0, ansb = 0;
for (int i = 19; i >= 0; i--)
{
if (disc[s][i] <= x && disc[s][i])
{
x -= disc[s][i];
ansa += disa[s][i];
ansb += disb[s][i];
s = C[s][i];
}
}
if (disa[s][0] <= x && a[s])//a能走就走走
ansa += disa[s][0];
long double ha = 0;
if (ansb == 0) ha = 2147483648788.00000000000000;//设为无穷大
else ha = (long double)(1.0 * ansa / ansb);
if( ha - minn < -0.0000000001 || (ha - minn <= -0.0000000001 && data[o] > data[mink]) )
minn = min(minn, ha), mink = o;
}
printf("%lld
", mink);
}
void s2()
{
while (m--)
{
int x, s, now, ansa = 0, ansb = 0;
scanf("%lld%lld", &s, &x);
for (int i = 19; i >= 0; i--)
{
if (disc[s][i] <= x && disc[s][i])
{
x -= disc[s][i];
ansa += disa[s][i];
ansb += disb[s][i];
s = C[s][i];
}
}
if (disa[s][0] <= x && a[s])//a能走就走走
ansa += disa[s][0];
printf("%lld %lld
", ansa, ansb);
}
}
signed main()//倍增优化链表，双向链表
{
init();
s1();
s2();
return 0;
}