题解 P1081 【开车旅行】
Hzxleo4
2017-09-16 10:39:51
个人认为思维难度挺大的题QAQ
思路就是倍增， 然而预处理就挺麻烦的， 要用 离散化 加 双向链表 处理出每一个点A和B要到的下一个点。
这里的处理要用到一些技巧， 详见代码。
然后就是倍增：
f[i][j] 表示 从第i个点出发， A和B没人开了（1<<j）天所到的点， stA(B)表示 A(B) 的 路程。
因为A是先走的， 所以要看最后一步A还能不能再走一步。
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n, m, l, r, j;
struct node{
int i, v, l, r;
bool operator < (const node & A) const{
return v < A.v;
}
}d[100005];
int h[100005], p[100005];
int stA[100005][21], stB[100005][21], f[100005][21];
int na[100005], nb[100005], a, b, ans = n;
double minn = 2147483647;
bool zuo(){
if(!l) return 0;
if(!r) return 1;
return d[j].v-d[l].v<=d[r].v-d[j].v;
}
int pd(int a, int b){
if(!a) return d[b].i;
if(!b) return d[a].i;
if(d[j].v-d[a].v <= d[b].v-d[j].v) return d[a].i;
return d[b].i;
}
void make_st(){
int i, j;
for(j = 1; j <= 19; j++){
for(i = 1; i <= n; i++){
f[i][j] = f[f[i][j-1]][j-1];
stA[i][j] = stA[i][j-1] + stA[f[i][j-1]][j-1];
stB[i][j] = stB[i][j-1] + stB[f[i][j-1]][j-1];
}
}
}
void getab(long long x, int p){
int i, j;
a = b = 0;
for(i = 19; i >= 0; i--){
if(f[p][i] && (long long)(a + b + stA[p][i]+stB[p][i]) <= x){
a += stA[p][i];
b += stB[p][i];
p = f[p][i];
}
}
if(na[p] && a + b + stA[p][0] <= x) a += stA[p][0];
}
int main(){
int i;
long long x;
scanf("%d", &n);
for(i = 1; i <= n; i++) scanf("%d", &d[i].v);
for(i = 1; i <= n; i++) d[i].i = i;
sort(d+1, d+i);
for(i = 1; i <= n; i++) p[d[i].i] = i;
for(i = 1; i <= n; i++) d[i].l = i-1, d[i].r = i+1;
d[1].l = d[n].r = 0;
for(i = 1; i <= n; i++){
j = p[i]; l = d[j].l; r = d[j].r;
if(zuo()) nb[i] = d[l].i, na[i] = pd(d[l].l, r);//左边的近
else nb[i] = d[r].i, na[i] = pd(l, d[r].r);//右边的近
if(l) d[l].r = r;//用完j要把j删除掉
if(r) d[r].l = l;
}
for(i = 1; i <= n; i++){
f[i][0] = nb[na[i]];
stA[i][0] = abs(d[p[i]].v - d[p[na[i]]].v);
stB[i][0] = abs(d[p[f[i][0]]].v - d[p[na[i]]].v);//记住结构体已经排序了， 所以要用他们的排名获取信息
}
make_st();
scanf("%lld%d", &x, &m);
for(i = 1; i <= n; i++){
getab(x, i);
if(b && 1.0*a/b < minn){
minn = 1.0*a/b;
ans = i;
}
}
printf("%d\n", ans);
for(i = 1; i <= m; i++){
scanf("%d%lld", &j, &x);
getab(x, j);
printf("%d %d\n", a, b);
}
return 0;
}
```