题解 P1081 【开车旅行】

龙啸空 · 2018-12-27 13:31:00 · 题解

这是一道需要用到大量STL优化的题目（不知道是不是自己太菜了）

用d[i][j]预处理从第i个城市向后走了2^j步，A和B开的距离

用dA[i][j]预处理从第i个城市向后走了2^j步，A开的距离

用nxtA[i][j]预处理出从第i个城市向后走了2^j步，A的后继的下标

用nxtB[i]预处理出从第i个城市，B的后继的下标

用一个map来存高度对应的下标，因为高度互不相同，所以不用担心查重的问题

再用一个set进行一个排序处理，从后向前进行处理，再定义一个set的指针，对这个高度进行二分，就可以方便的用logN的复杂度来找出他的两个后继了。

总体复杂度NlogN.

代码：

头文件和定义：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
using namespace std;
int nxtA[100005][21];
int nxtB[100005];
int dA[100005][21];
int d[100005][21];
int h[100005];
int N,M;
set<int> s;
set<int>::iterator p;
map<int,int> mp;
const long long INF = 1ll<<40;

预处理部分：

void init (){
    long long low1,low2,up1,up2;
    int idA,idB;
    for(int i=N;i>=1;i--){
        low1=low2=up1=up2=INF;
        mp[h[i]] = i;
        s.insert(h[i]);
        p = s.lower_bound(h[i]);
        int cnt = 0;
        if(p != s.begin()){
            --p;
            low1 = (*p);
            if(p != s.begin()){
                --p;
                low2 = (*p);
            }
        }
        p=s.upper_bound(h[i]);
        if(p != s.end()){
            up1 = (*p);
            ++p;
            if(p != s.end()){
                up2 = (*p);
            }
        }
        if(abs(h[i] - low1) <= abs(up1 - h[i])){
            nxtB[i] = mp[low1];
            if(abs(h[i] - low2) <= abs(up1 - h[i])){
                nxtA[i][0] = mp[low2];
            }else{
                nxtA[i][0] = mp[up1];
            }
        }else{
            nxtB[i] = mp[up1];
            if(abs(up2 - h[i])<abs(h[i] - low1)){
                nxtA[i][0] = mp[up2];
            }else{
                nxtA[i][0] = mp[low1];
            }
        }
        dA[i][0] = abs(h[i] - h[nxtA[i][0]]);
        d[i][0] = dA[i][0];
    }
    for(int j = 1; j <= 20; j++){
        for(int i = N;i >= 1; i--){
            if(j == 1){
                nxtA[i][j] = nxtB[nxtA[i][0]];
                dA[i][j] = abs(h[i] - h[nxtA[i][0]]);
                d[i][j] = dA[i][j] + abs(h[nxtA[i][0]]-h[nxtA[i][j]]);
            }else{
                nxtA[i][j] = nxtA[nxtA[i][j-1]][j-1];
                dA[i][j] = dA[i][j-1] + dA[nxtA[i][j-1]][j-1];
                d[i][j] = d[i][j-1] + d[nxtA[i][j-1]][j-1];
            }
        }
    }
}

工作部分：

long long disA,disB;
void work(int si,int xi){
    disA=0;
    disB=0;
    int p = si;
    for(int j = 20;j >= 0;j--){
        if(!nxtA[p][j] || d[p][j] > xi){
            continue;
        }
        xi -= d[p][j];
        disA += dA[p][j];
        disB += d[p][j] - dA[p][j];
        p = nxtA[p][j];
    }
}

主函数：

int main()
{
    scanf("%d",&N);
    for(int i = 1; i<= N; i++){
        scanf("%d",&h[i]);
    }
    init();
    int S,X;
    double ans = 1e70;
    double ans1 = 0;
    int idans;
    cin>>X;
    for(int i=1;i<=N;i++){
        work(i,X);
        if(disB == 0){
            ans1 = 1e40;
        }
        ans1 = disB==0?(double)INF:(double)disA/disB;
        if(!idans || ans1 < ans || (ans1 == ans && h[i] > h[idans])){
            ans = ans1;
            idans = i;
        }
    }
    cout<<idans<<endl;
    int Q;
    cin>>Q;
    while(Q--){
        cin>>S>>X;
        work(S,X);
        cout<<disA<<" "<<disB<<endl;
    }
    return 0;
}