题目链接：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 58 59 60 61 62 63 64 65 |
#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; } |
说点什么