给出n个排成一行的城市，每个城市有一个不同的海拔。定义两个城市间的距离等于他们的高度差的绝对值，且绝对值相等的时候海拔低的距离近。有两个人轮流开车，从左往右走。A每次都选最近的，B每次都选次近的。旅行时有一个总路程x，如果两个人的总路程>x 或 有一个人无法按照自己的原则选择目的城市，旅行就终止。
有两个问：
1.给出x0，求从哪一个城市出发，使得A走的路程/B走的路程最小。如果B走的路程=0，则比值视为无穷大。如果有多个城市满足要求，则输出海拔最高的那个城市。
2.给出x和s（出发城市），求旅行终止是A的路程和B的路程。
【数据范围】 对于30%的数据，有1≤N≤20，1≤M≤20； 对于40%的数据，有1≤N≤100，1≤M≤100； 对于50%的数据，有1≤N≤100，1≤M≤1,000； 对于70%的数据，有1≤N≤1,000，1≤M≤10,000； 对于100%的数据，有1≤N≤100,000，1≤M≤10,000，-1,000,000,000≤Hi≤1,000,000,000，0≤X0≤1,000,000,000，1≤Si≤N，0≤Xi≤1,000,000,000，数据保证Hi 互不相同。
先想骗分。。。
对于50%的数据还是很好骗的。每次旅行都直接模拟行走，每次找一个最近或次近，时间O(N*N)。
对于第一问直接枚举起点。时间复杂度为O(N*N*M + N*N*N)
发现50分算法主要是 每次都要找下一个城市 耗费了太多时间，于是干脆直接预处理，O(N*N)，总时间O(N*M + N*N)
还是想想改进。。。70分算法的预处理太傻逼了。。其实我们是要每次找到一个海拔与当前城市相差最少的城市。所以算法就有很多种了……比如离散化+链表，双向链表，平衡树（其实用set的话程序比双向链表还好打，因为二分stl都给你弄好了。。）
这里主要介绍下双向链表的做法：就是按高度排序，然后链起来。按城市原始位置从左到右处理接下来的城市是哪个，然后将自己删掉（因为接下来就没用了）。如何找接下来的那个？就是往链表的左右两边找两层，记一个最近和次近。
然后预处理就可以优化到O(N)
then？？？
发现其实这是一棵树。。。
于是倍增
预处理已经处理出2^0的情况了。接下来直接动规就好了，就可以预处理出每个点的2^i的父亲是谁，以及A走了多少，B走了多少。
then？？？
现在问题就是给定总路程要怎么求出AB走的路程。
问题可以转化成给定总路程求走了几次。然后就可以用上先前的预处理。假设走了t次，则t肯定可以表示成二进制，而且只有logn位的二进制数。于是可以枚举这一位取0还是1。调用先前处理的数组，看加上所增加的路程后会不会超出x，不会就是1，会就是0。
于是问题就完美解决了！
//代码（巨丑无比）
#include <cstdio> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> const int N = 100000 + 9; struct Link { int nxt,pre; }link[N]; int TOT,n,idx[N]; struct CITY { int h,idx; }city[N]; struct info { int 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){} }f[20][N][2]; //0: B //1: A inline bool cmp(const CITY &lhs,const CITY &rhs){return lhs.h < rhs.h;} inline int getnext(const int i,const int t){return i?t:(t^1);} void update(const int i,const int j,const int t) { const int nxt = f[i - 1][j][t].u; const long long dis1 = f[i - 1][j][t].dis1,dis2 = f[i - 1][j][t].dis2; if (nxt) { info tmp; if ((tmp = f[i - 1][nxt][getnext(i - 1,t)]).u) f[i][j][t] = info(tmp.u,dis1 + tmp.dis1,dis2 + tmp.dis2); } } std::pair<int,int> go(int s,long long x) { std::pair<int,int>tmp(0,0); int turn = 1; // A for (int i = TOT; i >= 0; --i) { if (!f[i][s][turn].u) continue; if (x - f[i][s][turn].dis1 - f[i][s][turn].dis2 < 0) continue; x -= f[i][s][turn].dis1 + f[i][s][turn].dis2; tmp.first += f[i][s][turn].dis2; tmp.second += f[i][s][turn].dis1; turn = getnext(i,turn); s = f[i][s][turn].u; } return 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(city[id_p].h - city[id_n].h); if (dis < Min_h1 || dis == Min_h1 && city[id_n].h < city[Min_i1].h) { Min_h2 = Min_h1; Min_i2 = Min_i1; Min_h1 = dis; Min_i1 = id_n; }else if (dis < Min_h2 || dis == Min_h2 && city[id_n].h < city[Min_i2].h) { Min_h2 = dis; Min_i2 = id_n; } } inline long long cmp2(const std::pair<int,int>lhs,const std::pair<int,int>rhs) { 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.second; } int main() { #ifndef ONLINE_JUDGE freopen("drive.in","r",stdin); freopen("drive.out","w",stdout); #endif scanf("%d",&n); for (int i = 1; i <= n; ++i) { scanf("%d",&city[i].h); city[i].idx = i; } std::sort(city + 1,city + 1 + n,cmp); for (int i = 1; i < n; ++i) { link[i].nxt = i + 1; link[i + 1].pre = i ; idx[city[i].idx] = i; } idx[city[n].idx] = n; for (int i = 1; i <= n; ++i) { int id = idx[i],Min_h1 = 0x7fffffff,Min_i1 = 0,Min_h2 = 0x7fffffff,Min_i2 = 0; check(id,link[id].pre, Min_h1, Min_i1, Min_h2, Min_i2); check(id,link[id].nxt, Min_h1, Min_i1, Min_h2, Min_i2); check(id,link[link[id].pre].pre, Min_h1, Min_i1, Min_h2, Min_i2); check(id,link[link[id].nxt].nxt, Min_h1, Min_i1, Min_h2, Min_i2); f[0][i][0] = info(city[Min_i1].idx,Min_h1,0); f[0][i][1] = info(city[Min_i2].idx,0,Min_h2); if (link[id].nxt) link[link[id].nxt].pre = link[id].pre; if (link[id].pre) link[link[id].pre].nxt = link[id].nxt; } TOT = static_cast<int>(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::pair<int,int>ans; int ans_pos = 0; ans.first = 1; ans.second = 0; for (int i = 1; i <= n; ++i) { std::pair<int,int>tmp = go(i,x); if (cmp2(tmp,ans) < 0) { ans = tmp; ans_pos = i; }else if (cmp2(tmp,ans) == 0 && city[idx[ans_pos]].h < city[idx[i]].h) { ans = tmp; ans_pos = i; } } printf("%d\n",ans_pos); int m; scanf("%d",&m); for (int i = 1,x,s; i <= m; ++i) { scanf("%d%d",&s,&x); std::pair<int,int> tmp = go(s,x); printf("%d %d\n",tmp.first,tmp.second); } }
转载于:https://www.cnblogs.com/lazycal/p/noip2012-day1-t3.html
相关资源：JAVA上百实例源码以及开源项目