NOIP 2012 Senior 3 - 开车旅行

还是太弱了…这道题拿到手上后完全没有能够在规定时间内解决的思路。不过还好，大体思路是对的：
首先预处理A、B在每个地方开一次车到达的地方。对于第一问，枚举A出发的位置，对于第二问，直接计算就行了。计算的方法就是挨着推，直到满足题目中结束旅行的条件。很明显，预处理的时间复杂度为$O(n^2)$，计算的时间复杂度为$O(n)$，因此整个程序的时间复杂度就为$O(n^2+n^2+nm)$，平方级的，按理说还能过个50~70分，但是可能比赛时计算比例那里写错了，最后只有35分。

这个题的思路就是这样，我们要做的就是将上面的两个操作至少优化到$O(n logn)$，幸运的是，这种算法是存在的。对于操作1，我们可以用一棵平衡树以$O(log n)$的时间复杂度完成操作，但我连平衡树都没有学过= =。幸运的是，STL有一个现成的平衡树set，使用它就已足够满足我们的要求了。
由于旅行只能从左往右走，因此我们只能从右往左向set中添加结点。假设有5座城市1,2,3,4,5，我们要计算A、B各自从3出发到达的下一个城市：

  3
 / 
4   5

这里假设4比3低，5比3高，那么树将会是以上这样。
我们可以使用set的find方法找到3的位置，然后对迭代器进行++,–，就能找到4,5了。
那么到底A该走哪里，B该走哪里呢？假设我们要计算1：

    1
   / 
  3   5              //这棵树是我乱编的
 /     
4       2

所以我们现在知道的是可能的答案为3,4,5,2，即向左扩展2个结点，向右扩展2个结点（想一想，为什么）。我们对这四个结点的进行排序，第0个就是B的目的地，第1个就是A的目的地。当然，如果A没有目的地，就不要改A。

对于计算这个操作，我们可以使用倍增的思想。之前我们一次走一步，时间复杂度为$O(n)$。倍增的思想就是花上$O(nlogn)$的时间进行预处理，使每次的查询时间将为$O(logn)$。对于这道题而言，可以这样定义：

next[k][i]代表从i出发，AB开了2^k轮车后到达的位置（一轮指AB先后开了一次车）
disA[k][i]代表从i出发，AB开了2^k轮车后A走的里程
disB[k][i]代表从i出发，AB开了2^k轮车后B走的里程
如果遇到最后只有A开了车，需要单独计算

有没有感觉这和ST表的定义很像？事实上，ST表就是用的倍增的思想。
枚举时，我们将k从大到小进行枚举（想一想，为什么不能从小到大）。如果开2^k轮车后能走到一个地方，则开，否则k--。k最终枚举到0，这毋庸置疑，那k从哪里开始枚举呢？我们可以从可能的极大值开始。因为如果k很大，肯定是开不到的，只是浪费一点时间而已。

最后，我们根据初始化的信息推算即可，详见代码。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
using std::cin;
using std::cout;
using std::endl;
#define FOR(x, f, t) for(int x = (f); x <= (t); x++)
inline int readIn()
{
    int a;
    scanf("%d",&a);
    return a;
}

const int maxn = 100005;
const int maxm = 100005;
int n,m;
struct CITY
{
    int index;
    int height;

    CITY(int index = 0, int height = 0):index(index), height(height)
    {

    }
    bool operator< (const CITY& b) const
    {
        return height < b.height;
    }
} cities[maxn];
int start[maxm];
int x[maxm];

int height;
struct sub   //用于初始化
{
    CITY destination;
    void operator=(const CITY& b)
    {
        destination = b;
    }
    bool operator<(const sub& b) const
    {
        int s1 = std::abs(height - destination.height);
        int s2 = std::abs(height - b.destination.height);
        if(s1==s2) return destination.height < b.destination.height;
        return s1<s2;
    }
} subs[4];
int nextA[maxn];
int nextB[maxn];
const int maxIndex = 17;
int next[maxIndex][maxn]; //从i开2^k轮后到的位置
long long disA[maxIndex][maxn]; //从i开2^k轮A的路程
long long disB[maxIndex][maxn]; //从i开2^k轮B的路程

void input()
{
    n=readIn();
    FOR(i, 1, n)
    {
        cities[i].height=readIn();
        cities[i].index = i;
    }
    x[0]=readIn();
    m=readIn();
    FOR(i, 1, m)
    {
        start[i]=readIn();
        x[i]=readIn();
    }
}
void init()
{
    std::set<CITY> des;
    des.insert(cities[n]);

    for(int i = n-1; i >= 1; i--)   //要从右往左更新，因为只能从左往右走
    {
        des.insert(cities[i]); //先插入：我们要知道要更新的城市的位置
        std::set<CITY>::iterator it = des.find(cities[i]); //要更新的城市的位置

        int nCmp = 0;
        if(it!=des.begin())
        {
            it--;
            subs[nCmp++] = *it;
            if(it!=des.begin())
            {
                it--;
                subs[nCmp++] = *it;
                it++;
            }
            it++;
        }
        if(it!=des.end())
        {
            it++; //不用复原了
            subs[nCmp++] = *it;
            if(it!=des.end())
            {
                it++;
                subs[nCmp++] = *it;
            }
        }

        height = cities[i].height;
        std::sort(subs, subs+nCmp);
        nextB[i] = subs[0].destination.index;
        if(i<=n-2) nextA[i] = subs[1].destination.index;
    }
}

void go(int from, int X, long long& lengthA, long long& lengthB)
{
    for(int i = maxIndex - 1; ~i; i--) //相当于二进制
    {
        if(next[i][from] && disA[i][from] + disB[i][from] <= X)
        {
            lengthA += disA[i][from];
            lengthB += disB[i][from];
            X -= disA[i][from] + disB[i][from];
            from = next[i][from];
        }
    }
    int last = nextA[from]; //看看A还能不能走
    if(!last) return;
    int lastDis = std::abs(cities[last].height - cities[from].height);
    if(lastDis <= X) lengthA+=lastDis;
}

void run()
{
    input();
    init(); //初始化A,B开一次开到哪里去了

    for(int i = 1; i <= n; i++) //初始化开1轮的情况
    {
        int pos1 = nextA[i];
        int pos2 = nextB[pos1];
        if(pos1) disA[0][i] = std::abs(cities[pos1].height - cities[i].height);
        if(pos2) disB[0][i] = std::abs(cities[pos2].height - cities[pos1].height);
        next[0][i] = pos2;
    }
    for(int i = 1; i <= maxIndex - 1; i++) //初始化开2^k轮的情况
    {
        for(int j = 1; j <= n; j++)
        {
            next[i][j] = next[i - 1][next[i - 1][j]];
            disA[i][j] = disA[i - 1][j] + disA[i - 1][next[i - 1][j]];
            disB[i][j] = disB[i - 1][j] + disB[i - 1][next[i - 1][j]];
        }
    }

    //solve1
    long long ansA=1e15;
    long long ansB=0;
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        long long lengthA=0, lengthB=0;
        go(i, x[0], lengthA, lengthB);
        if(lengthB && (!ans || ansA * lengthB > ansB * lengthA))
        {
            ans = i;
            ansA = lengthA;
            ansB = lengthB;
        }
    }
    printf("%dn",ans);

    //solve2
    for(int i = 1; i <= m; i++)
    {
        long long lengthA=0, lengthB=0;
        go(start[i], x[i], lengthA, lengthB);
        cout<<lengthA<<" "<<lengthB<<endl;
        printf("%lld %lldn",lengthA, lengthB);
    }
}

int main()
{
    run();
    return 0;
}

最后

以上就是清脆菠萝为你收集整理的NOIP 2012 Senior 3 - 开车旅行的全部内容，希望文章能够帮你解决NOIP 2012 Senior 3 - 开车旅行所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。