《noip2012 开车旅行 题解.doc》由会员分享，可在线阅读，更多相关《noip2012 开车旅行 题解.doc（5页珍藏版）》请在金锄头文库上搜索。
1、noip2012开车旅行 题解题目大意：给出n个排成一行的城市，每个城市有一个不同的海拔。定义两个城市间的距离等于他们的高度差的绝对值，且绝对值相等的时候海拔低的距离近。有两个人轮流开车，从左往右走。A每次都选最近的，B每次都选次近的。旅行时有一个总路程x，如果两个人的总路程x 或 有一个人无法按照自己的原则选择目的城市，旅行就终止。有两个问：1.给出x0，求从哪一个城市出发，使得A走的路程/B走的路程最小。如果B走的路程=0，则比值视为无穷大。如果有多个城市满足要求，则输出海拔最高的那个城市。2.给出x和s（出发城市），求旅行终止是A的路程和B的路程。 题解：【数据范围】 对于30%的数据，
2、有1N20，1M20； 对于40%的数据，有1N100，1M100； 对于50%的数据，有1N100，1M1,000； 对于70%的数据，有1N1,000，1M10,000； 对于100%的数据，有1N100,000，1M10,000，-1,000,000,000Hi1,000,000,000，0X01,000,000,000，1SiN，0Xi1,000,000,000，数据保证Hi 互不相同。 先想骗分。50分对于50%的数据还是很好骗的。每次旅行都直接模拟行走，每次找一个最近或次近，时间O(N*N)。对于第一问直接枚举起点。时间复杂度为O(N*N*M + N*N*N)70分发现50分算法主
3、要是 每次都要找下一个城市 耗费了太多时间，于是干脆直接预处理，O(N*N)，总时间O(N*M + N*N)满分还是想想改进。70分算法的预处理太傻逼了。其实我们是要每次找到一个海拔与当前城市相差最少的城市。所以算法就有很多种了比如离散化+链表，双向链表，平衡树（其实用set的话程序比双向链表还好打，因为二分stl都给你弄好了。）这里主要介绍下双向链表的做法：就是按高度排序，然后链起来。按城市原始位置从左到右处理接下来的城市是哪个，然后将自己删掉（因为接下来就没用了）。如何找接下来的那个？就是往链表的左右两边找两层，记一个最近和次近。然后预处理就可以优化到O(N)then？发现其实这是一棵树。
4、于是倍增预处理已经处理出20的情况了。接下来直接动规就好了，就可以预处理出每个点的2i的父亲是谁，以及A走了多少，B走了多少。then？现在问题就是给定总路程要怎么求出AB走的路程。问题可以转化成给定总路程求走了几次。然后就可以用上先前的预处理。假设走了t次，则t肯定可以表示成二进制，而且只有logn位的二进制数。于是可以枚举这一位取0还是1。调用先前处理的数组，看加上所增加的路程后会不会超出x，不会就是1，会就是0。于是问题就完美解决了！代码（巨丑无比）/看完后麻烦帮忙下下来棒忙加点财富。大家也可以加点人品。#include #include #include #include #inclu
5、de const int N = 100000 + 9;struct Linkint nxt,pre;linkN;int TOT,n,idxN;struct CITYint h,idx;cityN;struct infoint u;long long dis1,dis2;info(const int a = 0,const long long b = 0,const long long c = 0):u(a),dis1(b),dis2(c)f20N2;/0: B/1: Ainline bool cmp(const CITY &lhs,const CITY &rhs)return lhs.h r
6、hs.h;inline int getnext(const int i,const int t)return i?t:(t1);void update(const int i,const int j,const int t)const int nxt = fi - 1jt.u;const long long dis1 = fi - 1jt.dis1,dis2 = fi - 1jt.dis2;if (nxt) info tmp;if (tmp = fi - 1nxtgetnext(i - 1,t).u)fijt = info(tmp.u,dis1 + tmp.dis1,dis2 + tmp.di
7、s2);std:pair go(int s,long long x)std:pairtmp(0,0);int turn = 1; / Afor (int i = TOT; i = 0; -i) if (!fisturn.u) continue;if (x - fisturn.dis1 - fisturn.dis2 0) continue;x -= fisturn.dis1 + fisturn.dis2;tmp.first += fisturn.dis2;tmp.second += fisturn.dis1;turn = getnext(i,turn);s = fisturn.u;return
8、tmp;inline void check(const int id_p,const int id_n,int &Min_h1,int &Min_i1,int &Min_h2,int &Min_i2)if (!id_n) return;const int dis = std:abs(cityid_p.h - cityid_n.h);if (dis Min_h1 | dis = Min_h1 & cityid_n.h cityMin_i1.h) Min_h2 = Min_h1;Min_i2 = Min_i1;Min_h1 = dis;Min_i1 = id_n;else if (dis Min_
9、h2 | dis = Min_h2 & cityid_n.h cityMin_i2.h) Min_h2 = dis;Min_i2 = id_n;inline long long cmp2(const std:pairlhs,const std:pairrhs)if (!lhs.second & !rhs.second) return 0;else if (!lhs.second) return 1;else if (!rhs.second) return -1;else return 1ll * lhs.first * rhs.second - 1ll * rhs.first * lhs.se
10、cond;int main()#ifndef ONLINE_JUDGEfreopen(drive.in,r,stdin);freopen(drive.out,w,stdout);#endifscanf(%d,&n);for (int i = 1; i = n; +i) scanf(%d,&cityi.h);cityi.idx = i; std:sort(city + 1,city + 1 + n,cmp);for (int i = 1; i n; +i) linki.nxt = i + 1;linki + 1.pre = i ;idxcityi.idx = i;idxcityn.idx = n
11、;for (int i = 1; i = n; +i) int id = idxi,Min_h1 = 0x7fffffff,Min_i1 = 0,Min_h2 = 0x7fffffff,Min_i2 = 0;check(id,linkid.pre, Min_h1, Min_i1, Min_h2, Min_i2);check(id,linkid.nxt, Min_h1, Min_i1, Min_h2, Min_i2);check(id,linklinkid.pre.pre, Min_h1, Min_i1, Min_h2, Min_i2);check(id,linklinkid.nxt.nxt,
12、Min_h1, Min_i1, Min_h2, Min_i2);f0i0 = info(cityMin_i1.idx,Min_h1,0);f0i1 = info(cityMin_i2.idx,0,Min_h2);if (linkid.nxt) linklinkid.nxt.pre = linkid.pre;if (linkid.pre) linklinkid.pre.nxt = linkid.nxt;TOT = static_cast(ceil(log2(double)n);for (int i = 1; i = TOT; +i)for (int j = 1; j = n; +j) update(i,j,0);update(i,j,1);int x;scanf(%d,&x);std:pairans;int ans_pos = 0;ans.first = 1; ans.second = 0;for (int i = 1; i = n; +i) std:pairtmp = go(i,x);if (
