洛谷P1081开车旅行题解--zhengjun
题面传送门
我天，搞死我了，细节不少啊
思路首先，一定会看出来可以在暴力的基础上加一点优化——预处理出每个点的第一近的点和第二近的点。(我枯了)
然后，弄好之后，我们发现，如果从不同点开始，有可能还是会走到一起，(即为后面一段相同)，所以，就有了另一个优化——倍增，如果还不会的话，可以看看rmqrmqrmq，ststst表。
就是用fi,jf_{i,j}fi,j表示从iii点开始，走2j2^j2j轮到的点，这样，就可以优化成logloglog级别的了。
其实这个数组很好处理，还是前面的预处理好难啊。
#include
#define maxn 100002
using namespace std;
int n;
struct zj{
int h,num,l,r;
bool operator < (const zj &x)const{
return h=0;i--){
if(f[p][i]>0&&(long long)aa+bb+fa[p][i]+fb[p][i]0&&(long long)aa+bb+fa[p][0]<=x)aa+=fa[p][0];
}
int abs(int x){return x<0?-x:x;}
bool check(int now,int l,int r){
if(!l)return 0;
if(!r)return 1;
return abs(a[l].h-a[now].h)<=abs(a[r].h-a[now].h);
}
int which(int now,int l,int r){
if(!l)return a[r].num;
if(!r)return a[l].num;
if(abs(a[l].h-a[now].h)<=abs(a[r].h-a[now].h))return a[l].num;
return a[r].num;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i].h),a[i].num=i;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)get[a[i].num]=i,a[i].l=i-1,a[i].r=i+1;
a[1].l=a[n].r=0;//链表,会快很多
for(int i=1;i<=n;i++){
int now=get[i];//找到排序之后的
int l=a[now].l,r=a[now].r;
if(check(now,l,r)){
f1[i]=a[l].num;
f2[i]=which(now,a[l].l,r);
}
else{
f1[i]=a[r].num;
f2[i]=which(now,l,a[r].r);
}
if(l)a[l].r=r;
if(r)a[r].l=l;
}
for(int i=1;i<=n;i++){
f[i][0]=f1[f2[i]];
fa[i][0]=abs(a[get[i]].h-a[get[f2[i]]].h);
fb[i][0]=abs(a[get[f[i][0]]].h-a[get[f2[i]]].h);
}
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
fa[i][j]=fa[i][j-1]+fa[f[i][j-1]][j-1];
fb[i][j]=fb[i][j-1]+fb[f[i][j-1]][j-1];
}
}
long long x;
int k=-1;
double minx=1e10;
scanf("%lld",&x);
for(int i=1;i0&&(double)aa/bb<minx){
minx=(double)aa/bb;
k=i;
}
}
printf("%d\n",k);
int m,s;
scanf("%d",&m);
while(m--){
scanf("%d%lld",&s,&x);
getans(x,s);
printf("%d %d\n",aa,bb);
}
return 0;
}
谢谢–zhengjun
作者：A_zjzj
