http://acm.timus.ru/problem.aspx?space=1&num=2064
题意：有n只虫子在爬树，每个虫子往上爬ti距离后会往下掉落ti距离，每爬一个单位距离耗费一个单位时间，然后重新往上爬。有q个询问，询问当前的x时刻，爬的最高的虫子所在的最高位置。
思路：画个以时间为x轴，距离为y轴的图，可以清楚知道整个图是类似于一座座山峰的。我们只要处理每个时刻的最高点。
只考虑最高点所在的位置，处理出虫子能达到的最高点的时刻的最高点arrive[]。
考虑每个时刻要得到最优的两种情况：假设当前时刻为x。
1、第一种是某只虫子正在往上爬。这种情况可以考虑成时间逆流地往下掉。时间从后往前扫，对于每个时刻求出最大的arrive[i] - (i - x)。i代表之前某只虫子某个能达到的最高点的时刻。
2、第二种是某只虫子正在往下掉。这种情况将时间从前往后扫，对于每个时刻求出最大的arrive[i] - (x - i)。i的含义同上。
因为时间只有1e6，可以从后往前扫（处理出往上爬的情况）再从前往后（处理往下掉的情况）扫所有时间，处理出ans[]表。对于询问O（1）回答。
而且这题用scanf超时，用读入外挂偶尔超时，看别人代码用了“ios::sync_with_stdio(false);”取消同步，不会超时。
玄学。不懂。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 1000100 4 #define M 1000004 5 #define INF 0x3f3f3f3f 6 int arrive[N], ans[N]; 7 8 int main() { 9 ios::sync_with_stdio(false); 10 int n, t, tid, q; 11 cin >> n; 12 bool flag = 0; 13 for(int i = 1; i <= n; i++) { 14 cin >> t; if(t >= M) flag = 1; 15 for(tid = t; tid <= M; tid += 2 * t) 16 if(arrive[tid] < t) arrive[tid] = t; // arrive[tid]记录tid时刻能达到的最大高度 17 if(arrive[M] < t - (tid - M)) arrive[M] = t - tid + M; // 终点向下掉 18 } 19 for(t = 1, tid = -INF; t <= M; t++) { 20 // 时间正着往下掉: (i < t)ans[t] = max(ans[t], arrive[i] + i - t); 21 if(tid < arrive[t] + t) tid = arrive[t] + t; // 记录目前最大的arrive[i]+i 22 if(ans[t] < tid - t) ans[t] = tid - t; 23 } 24 for(t = M, tid = -INF; t >= 1; t--) { 25 // 时间逆着往下掉(向上爬): (t < i)ans[t] = max(ans[t], arrive[i] - i + t); 26 if(tid < arrive[t] - t) tid = arrive[t] - t; // 记录之前最大的arrive[i]-i 27 if(ans[t] < tid + t) ans[t] = tid + t; 28 } 29 cin >> q; 30 while(q--) { 31 cin >> t; 32 if(flag) cout << t << ‘\n‘; 33 else cout << ans[t] << ‘\n‘; 34 } 35 return 0; 36 }
原文：http://www.cnblogs.com/fightfordream/p/6409588.html