B - Help Jimmy
Time Limit: 1000/1000MS (C++/Others) Memory Limit: 65536/65536KB (C++/Others)
Problem Description
"Help Jimmy" 是在下图所示的场景上完成的游戏：
场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。
Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。
设计一个程序，计算Jimmy到地面时可能的最早时间。
Input
第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。1<= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）。所有坐标的单位都是米。
Jimmy 的大小和平台的厚度均忽略不计。如果Jimmy 恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy一定能安全到达地面。
Output
对输入的每组测试数据，输出一个整数，Jimmy到地面时可能的最早时间。
Sample Input
1 3 8 17 20 0 10 8 0 10 13 4 14 3Sample Output
23
#include<cstdio> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; // 表示无限大 大约是1e9多一点 struct Node { // 结构体数组用于记录每个位置的状态 int l, r, h; // 当前位置的左右端点、高度 int t, lt, rt; // 到达当前位置的时间、到达当前位置左右端点的时间 bool operator < (const Node& b) const{ // 重载运算符用于排序，按照高度降序排序 return h > b.h; } }a[1005]; int main() { int T, n, x, y, max; scanf("%d", &T); while(T--) { // T组测试样例 scanf("%d%d%d%d", &n, &x, &y, &max); a[0].l = a[0].r = x; a[0].t = a[0].lt = a[0].rt = 0; a[0].h = y; // 给a[0]赋值，代表初始的位置，左右边界都是x，左右时间都是0，高度为y for(int i=1; i<=n; i++) scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].h); // 输入每个平台的左右端点和高度，下标[1, n] a[n+1].l = -20000; a[n+1].r = 20000; a[n+1].h = 0; // 给a[n+1]赋值，左右边界都到题目要求的最大值，表示地面 sort(a, a+n+2); // 按照高度降序，给n+2个元素排序 for(int i=1; i<n+2; i++){ // 按照高度降序，计算到达平台的时间 a[i].t = a[i].lt = a[i].rt = inf; // 到达平台的时间一开始置为无限大 for(int j=i-1; j>=0; j--){ // 必须是倒序遍历，因为里面有break if(a[j].h - a[i].h > max) break; // 超过高度则跳出，因为降序 if(a[j].l >= a[i].l && a[j].l <= a[i].r){ // a[j]从左侧落下可以落在i上 int down_time = a[j].h - a[i].h; // 下落时间 int movel_time = a[j].l - a[i].l; // 下落后，移动到左端点的时间 int mover_time = a[i].r - a[j].l; // 下落后，移动到右端点的时间 // 更新取min a[i].t = min(a[i].t, a[j].lt + down_time); a[i].lt = min(a[i].lt, a[j].lt + down_time + movel_time); a[i].rt = min(a[i].rt, a[j].lt + down_time + mover_time); a[j].l = -20001; // 因为从从a[j]下落后一定只能落在一个平台上， // 为了避免重复，把a[j]的左端点置为最小值 } if(a[j].r >= a[i].l && a[j].r <= a[i].r){ // a[j]从右侧落下可以落在i上， // 一定不能用else if int down_time = a[j].h - a[i].h; int movel_time = a[j].r - a[i].l; int mover_time = a[i].r - a[j].r; a[i].t = min(a[i].t, a[j].rt + down_time); a[i].lt = min(a[i].lt, a[j].rt + down_time + movel_time); a[i].rt = min(a[i].rt, a[j].rt + down_time + mover_time); a[j].r = 20001; } } } printf("%d ", a[n+1].t); // 输出到达地面的时间即可 } return 0; }