题目链接：HDU 6695
题目要求把元素分成两个集合\(A,B\)，一个集合只能用\(x\)属性，另一个只能用\(y\)属性，要求\(\min | \max A_i(x)- \max B_i(x) |\)
以\(x\)属性为关键字进行排序（从小到大），从前往后枚举，假设第\(i\)个放在第一个集合里且是最大的，后面的元素就只能放在第二个集合里面。
讨论\(B\)集合中最大的元素是什么，假设\(m\)为\(y[i+1 \cdots n]\)的后缀最大值，如果\(x_i \leq m\)，那么一定是选择\(m\)，否则可以在前面的\(y\)当中选最接近\(x_i\)的，具体方法是在平衡树中二分。
这种固定一个求另一个的方法是一种常见方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
struct Node {
LL x, y;
inline void input() {
scanf("%lld%lld", &x, &y);
}
friend bool operator < (const Node &u, const Node &v) {
return u.x < v.x;
}
} a[MAX_N];
LL T, n, suf[MAX_N];
multiset <LL> s;
inline LL getAbs(LL u) {
return u < 0 ? -u : u;
}
void cal() {
LL minDelt = LL(1E18);
for (int i = 1; i <= n; ++i) {
LL sufMax = suf[i + 1];
LL now = a[i].x;
if (now <= sufMax) minDelt = min(minDelt, getAbs(now - sufMax));
else {
auto minIt = s.lower_bound(now);
if (i != n) minDelt = min(minDelt, getAbs(now - sufMax));
if (minIt == s.end()) {
if (s.size()) {
--minIt;
if (*minIt > sufMax) minDelt = min(minDelt, getAbs(now - *minIt));
}
} else {
if (*minIt > sufMax) minDelt = min(minDelt, getAbs(now - *minIt));
if (minIt != s.begin()) {
--minIt;
if (*minIt > sufMax) minDelt = min(minDelt, getAbs(now - *minIt));
}
}
}
s.insert(a[i].y);
}
printf("%lld\n", minDelt);
}
int main() {
scanf("%lld", &T);
for (int cs = 1; cs <= T; ++cs) {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) a[i].input();
sort(a + 1, a + n + 1);
suf[n + 1] = -1;
for (int i = n; i >= 1; --i) suf[i] = max(a[i].y, suf[i + 1]);
s.clear();
cal();
}
return 0;
}
|