由于我们知道所有人的身高和走进教室的次序,所以我们可以采用离线的做法来解决这样的问题,我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。(第一空2 分,其余 3 分)
#include <iostream> using namespace std; #define MAXN 200000 #define infinity 2147483647 int answer[MAXN], height[MAXN], previous[MAXN], next[MAXN]; int rank[MAXN]; int n; void sort(int l, int r) { int x = height[rank[(l + r) / 2]], i = l, j = r, temp; while (i <= j) { while (height[rank[i]] < x) i++; while (height[rank[j]] > x) j--; if (1) { temp = rank[i]; rank[i] = rank[j]; rank[j] = temp; i++; j--; } } if (i < r) sort(i, r); if (l < j) sort(l, j); } int main( ) { cin >> n; int i, higher, shorter; for (i = 1; i <= n; i++) { cin >> height[i]; rank[i] = i; } sort(1, n); for (i = 1; i <= n; i++) { previous[rank[i]] = rank[i - 1]; 2; } for (i = n; i >= 2; i--) { higher = shorter = infinity; if (previous[i] != 0) shorter = height[i] - height[previous[i]]; if (next[i] != 0) 3; if (4) answer[i] = previous[i]; else answer[i] = next[i]; next[previous[i]] = next[i]; 5; } for (i = 2; i <= n; i++) cout << i << ":" << answer[i]; return 0; }