UVA-11134 传说中的车 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版x坐标和y坐标是独立的而且处理方式一致。实际上就是n个区间有n个点让每个点分配到一个区间内部。一开始我想对区间排序对右侧坐标从小到大排序右侧坐标相同时再对左侧坐标排序。然后后一个区间分配的点肯定比前一个区间的点靠后因此一个点一个点赋值即可。但后来发现这样结果不对。例如:区间1 [1, 10]区间2 [10, 10]区间3 [1, 11]如果按照排序后一个一个赋值则结果为110 11但是这样中间出现空档明显结果不正确。又发现按照数字规模其实可以遍历整个坐标不超时因此对整个区间遍历寻找即可。AC代码#include stdio.h #include string.h #include stdlib.h int n; struct Rect { int xl, yl, xr, yr; int num; int x, y; }; Rect arr[5500]; int arrMap[5500]; int compareX(const void *left, const void *right) { const Rect *l (const Rect *)left; const Rect *r (const Rect *)right; if (l-xr ! r-xr) { return l-xr - r-xr; } return l-xl - r-xl; } bool computedX() { int i, j; int flag 0; qsort(arr, n, sizeof(Rect), compareX); memset(arrMap, 0, sizeof(arrMap)); for (i 0; i n; i) { flag 0; for (j arr[i].xl; j arr[i].xr; j) { if (!arrMap[j]) { arr[i].x j; flag 1; arrMap[j] 1; break; } } if (flag 0) return false; } return true; } int compareY(const void *left, const void *right) { const Rect *l (const Rect *)left; const Rect *r (const Rect *)right; if (l-yr ! r-yr) { return l-yr - r-yr; } return l-yl - r-yl; } bool computedY() { int i, j; int flag 0; qsort(arr, n, sizeof(Rect), compareY); memset(arrMap, 0, sizeof(arrMap)); for (i 0; i n; i) { flag 0; for (j arr[i].yl; j arr[i].yr; j) { if (!arrMap[j]) { arr[i].y j; flag 1; arrMap[j] 1; break; } } if (flag 0) return false; } return true; } int compareIndex(const void *left, const void *right) { const Rect *l (const Rect *)left; const Rect *r (const Rect *)right; return l-num - r-num; } int main() { int xl, yl, xr, yr, i, j; while (scanf(%d, n) 0 n 0) { memset(arr, 0, sizeof(arr)); for (i 0; i n; i) { scanf(%d %d %d %d, xl, yl, xr, yr); arr[i] {xl - 1, yl - 1, xr - 1, yr - 1, i, -1, -1}; } if (!computedX() || !computedY()) { printf(IMPOSSIBLE\n); continue; } qsort(arr, n, sizeof(Rect), compareIndex); for (i 0; i n; i) { printf(%d %d\n, arr[i].x 1, arr[i].y 1); } } return 0; }