企业官网建设流程全解析

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

x坐标和y坐标是独立的，而且处理方式一致。

实际上就是n个区间，有n个点，让每个点分配到一个区间内部。

一开始我想对区间排序，对右侧坐标从小到大排序，右侧坐标相同时，再对左侧坐标排序。

然后后一个区间分配的点，肯定比前一个区间的点靠后，因此一个点一个点赋值即可。但后来发现这样结果不对。

例如:

区间1 [1, 10]

区间2 [10, 10]

区间3 [1, 11]

如果按照排序后一个一个赋值，则结果为1，10， 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; }