题解 P1081 【开车旅行】

muller · 2019-02-17 16:20:29 · 题解

这题直接倍增dp吧

好像有点难写

就是注意他的dp状态

首先预处理出从每个点出发如果是A走到哪个点，

如果是B走到哪个点。 然后利用刚刚预处理出的信息再预处理从每个点出发A走2i

就是有点麻烦，如果暴力找会tle

所以用平衡树或set维护一下

寻到最小值直接倍增一下，有点像rmq求嘴值

其实会的话还是挺好写的

于是开始瞎搞

1.5h终于a掉

%%%%%%%%%dtkjd 15minA题，博客上提示我做法

丑陋无比的代码：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005,K=21;
struct data{
    int height,id;
    friend bool operator < (data a,data b){return a.height<b.height;}
} a[N];
ll n,T,ans,x0,si,xi,ga[N],gb[N],x,y,f[N][K],da[N][K],db[N][K];
set<data> s;
pair<ll,ll> tmp;
bool cmp(data x,data y){
    if (x.height!=y.height) return x.height<y.height;
    return a[x.id].height<a[y.id].height;
}
void get(ll id){
    ll len=0;set<data>::iterator it;
    data tmp[10];it=s.find(a[id]);
    if (it!=s.begin()){
        it--;tmp[++len]=(data){a[id].height-it->height,it->id};
        if (it!=s.begin()){it--;tmp[++len]=(data){a[id].height-it->height,it->id};   it++;}    
        it++;
    }
    it++;
    if (it!=s.end()) {
        tmp[++len]=(data){it->height-a[id].height,it->id};it++;
        if (it!=s.end()) tmp[++len]=(data){it->height-a[id].height,it->id};
    }
    sort(tmp+1,tmp+len+1,cmp);ga[id]=tmp[1].id;
    if (len==1) return;
    gb[id]=tmp[2].id;
}
inline pair<ll,ll> ask(ll pos,ll d){
    ll ans1=0,ans2=0;
    for (int i=K-1;i>=0;i--) if (f[pos][i]&&ans1+ans2+da[pos][i]+db[pos][i]<=d){ans1+=da[pos][i];ans2+=db[pos][i];pos=f[pos][i];}
    if (gb[pos]){if (ans1+ans2+abs(a[pos].height-a[gb[pos]].height)<=d) ans1+=abs(a[pos].height-a[gb[pos]].height);}
    return make_pair(ans1,ans2);
}
int main(){
    scanf("%lld",&n);
    for (int i=1;i<=n;i++){scanf("%lld",&a[i].height);a[i].id=i;}
    for (int i=n;i;i--){s.insert(a[i]);if (i!=n) get(i);   }
    for (int i=1;i<=n;i++){
        f[i][0]=ga[gb[i]];
        if (gb[i]) da[i][0]=abs(a[i].height-a[gb[i]].height);
        if (gb[i]&&ga[gb[i]]) db[i][0]=abs(a[gb[i]].height-a[ga[gb[i]]].height);    
    }
    for (int j=1;j<K;j++)
    for (int i=1;i<=n;i++){f[i][j]=f[f[i][j-1]][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];}
    scanf("%lld",&x0);ans=x=y=0;
    for (int i=1;i<=n;i++){
        tmp=ask(i,x0);
        if (tmp.second!=0&&(!ans || tmp.first*y<tmp.second*x)){ans=i;x=tmp.first;y=tmp.second;}
    }
    printf("%lld\n",ans);scanf("%lld",&T);
    while (T--){
        scanf("%lld%lld",&si,&xi);tmp=ask(si,xi);
        printf("%lld %lld\n",tmp.first,tmp.second);
    }
    return 0;
}