洛谷1081 开车旅行

Luogu

分析

思路比较简单但是代码细节很多的一道题...

首先预处理出每个点后面的最近的点和次近的点。这个可以使用 set 或者双端链表。

然后预处理一下每个点往后走 $2^k$ 轮(一轮表示 A 开一天、B 开一天)后到的点、A 开的路程、B 开的路程。这个就是简单的倍增。

然后就很简单了。注意倍增是一轮一轮的跳的,所以跳完后 A 可能还可以再开一天。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q;

struct city { int h,id; } a[N];
set<city> S;
vector<city> vec;
bool operator <(city y,city x) { return x.h<y.h; }
inline int cmp(city x,city y) {
    if (x.h!=y.h) return x.h<y.h;
    else return a[x.id].h<a[y.id].h;
}

int mn[N],mn2[N];
int f[17][N],fa[17][N],fb[17][N];

inline pair<int,int> query(int s,int x) {
    pair<int,int> res=make_pair(0,0);
    for (re int i=16;~i;--i)
        if (fa[i][s]+fb[i][s]<=x) {
            res.first+=fa[i][s],res.second+=fb[i][s];
            x-=fa[i][s]+fb[i][s];
            s=f[i][s];
        }
    if (mn[s]&&fa[0][s]<=x) res.first+=fa[0][s];
    return res;
}

signed main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=(city){read(),i};
    S.insert(a[n]);
    for (re int i=n-1;i;--i) {
        S.insert(a[i]); vec.clear();
        auto it=S.find(a[i]);
        if (it!=S.begin()) {
            --it,vec.push_back((city){abs(a[i].h-it->h),it->id});
            if (it!=S.begin())
                --it,vec.push_back((city){abs(a[i].h-it->h),it->id}),++it;
            ++it;
        }
        ++it;
        if (it!=S.end()) {
            vec.push_back((city){abs(a[i].h-it->h),it->id}),++it;
            if (it!=S.end())
                vec.push_back((city){abs(a[i].h-it->h),it->id});
        }
        sort(vec.begin(),vec.end(),cmp);
        mn[i]=vec[0].id; if (vec.size()>1) mn2[i]=vec[1].id;
    }
    for (re int i=1;i<=n;++i) {
        int p=mn2[i],q=mn[p]; f[0][i]=q;
        if (p) fa[0][i]=abs(a[i].h-a[p].h);
        if (q) fb[0][i]=abs(a[p].h-a[q].h);
    }
    for (re int i=1;i<17;++i)
        for (re int j=1;j<=n;++j) {
            f[i][j]=f[i-1][f[i-1][j]];
            fa[i][j]=fa[i-1][j]+fa[i-1][f[i-1][j]];
            fb[i][j]=fb[i-1][j]+fb[i-1][f[i-1][j]];
        }
    int X0=read(),ansa=2e9,ansb=1,ansp=0;
    for (re int i=1;i<=n;++i) {
        auto res=query(i,X0); int nowa=res.first,nowb=res.second;
        if (nowb&&nowa*ansb<ansa*nowb) ansa=nowa,ansb=nowb,ansp=i;
        else if (nowb&&nowa*ansb==ansa*nowb&&a[i].h>a[ansp].h) ansp=i;
    }
    printf("%lld\n",ansp);
    Q=read();
    while (Q--) {
        int s=read(),x=read();
        auto res=query(s,x);
        printf("%lld %lld\n",res.first,res.second);
    }
    return 0;
}
最后修改:2019 年 11 月 05 日 03 : 21 PM

发表评论