pku 1661 Help Jimmy

骑猪看日落 2022-08-13 21:00 25阅读 0赞

\#include <iostream> \#include <climits> \#include <algorithm> using namespace std; struct Board \{ int left, right; int height; \}; Board board\[1005\]; int Left\[1005\], Right\[1005\]; int n; int N, X, Y, MAX; \#define INTMAX INT\_MAX/10 bool cmp(const Board& lhs, const Board& rhs) \{ if(lhs.height > rhs.height) return true; else if(lhs.height == rhs.height && lhs.left < rhs.left) return true; else return false; \} inline int min(const int& lhs, const int& rhs) \{ return lhs < rhs ? lhs:rhs; \} inline bool notBeCovered(int p, int i, int j) \{ for(int k = i-1; k >= j+1; --k) if(board\[k\].left <= p && board\[k\].right >= p) return false; return true; \} inline bool canGoToGroud(int p, int i) \{ for(int k = i+1; k <= N; k++) if(board\[k\].left <= p && board\[k\].right >= p) return false; return true; \} int main() \{ scanf("%d", &n); while(n--) \{ scanf("%d%d%d%d", &N, &X, &Y, &MAX); for(int i = 1; i <= N; ++i) scanf("%d%d%d", &board\[i\].left, &board\[i\].right, &board\[i\].height); sort(board+1, board+N+1, cmp); memset(Left, 0x7777, sizeof(Left)); memset(Right, 0x7777, sizeof(Right)); board\[0\].left = board\[0\].right = X; board\[0\].height = Y; Left\[0\] = Right\[0\] = 0; for(int i = 1; i <= N; ++i) \{ int min1 = INTMAX, min2 = INTMAX; for(int j = i-1; j >= 0; j--) if(board\[j\].height - board\[i\].height > 0 && board\[j\].height - board\[i\].height <= MAX) \{ int temp1 = INTMAX; if(board\[j\].left <= board\[i\].right&&board\[j\].left >= board\[i\].left && notBeCovered(board\[j\].left, i, j)) temp1 = min(temp1, board\[j\].left-board\[i\].left+Left\[j\]); if(board\[j\].right <= board\[i\].right&&board\[j\].right >= board\[i\].left && notBeCovered(board\[j\].right, i, j)) temp1 = min(temp1, board\[j\].right-board\[i\].left+Right\[j\]); if(temp1 < min1) min1 = temp1; int temp2 = INTMAX; if(board\[j\].left <= board\[i\].right&&board\[j\].left >= board\[i\].left && notBeCovered(board\[j\].left, i, j)) temp2 = min(temp2, board\[i\].right-board\[j\].left+Left\[j\]); if(board\[j\].right <= board\[i\].right&&board\[j\].right >= board\[i\].left && notBeCovered(board\[j\].right, i, j)) temp2 = min(temp2, board\[i\].right-board\[j\].right+Right\[j\]); if(temp2 < min2) min2 = temp2; \} Left\[i\] = min1, Right\[i\] = min2; \} int Min = INTMAX; for (int i = 0; i <= N; ++i) \{ if(board\[i\].height <= MAX) \{ if(canGoToGroud(board\[i\].left, i) && Left\[i\] < Min) Min = Left\[i\]; if(canGoToGroud(board\[i\].right, i) && Right\[i\] < Min) Min = Right\[i\]; \} \} printf("%d/n", Min+Y); \} return 0; \} /\* 思路相对比较简单: 设到达第i个板左端的最短时间Left\[i\], 到达第i个板右端的最短时间Right\[i\]; 所求即为每条可以到达地面的板(包括初始位置)的最小值 (其中要刨去超过MAX的). //此题需要注意的地方颇多: 1. INTMAX 不可取INT\_MAX, 否则INT\_MAX再加上一个数可能溢出变成负数, 以后做题时也一定要注意!!! 2. 注意Jimmy可以直接到地面的情形, 即: for (int i = 1; i <= N; ++i) => for (int i = 0; i <= N; ++i) 3.要判断Jimmy初始位置能否到达该板: for(int i = 1; i <= N; ++i) \{ int min1 = INTMAX, min2 = INTMAX; for(int j = i-1; j >= 0; j--) ... \} 4. 判断每个板是否能否直接到地面时, 不要忘记高度限制, 我就在这WA了2次: for (int i = 0; i <= N; ++i) \{ if(board\[i\].height <= MAX) .... \} \*/