感觉最近有点颓废啊。水几篇题解。
简而言之，就是你希望把 个元素分成 组，使得每组中 。
对于这种限制我们通常先按照某一个维度排序，这样通常可以方便处理一点。
我们先考虑按照 从大到小进行排序，按照 排序似乎不太好做（或许只是因为我太菜了）。排序之后，我们就只需要考虑最后一个元素的限制了。
我们拿到一个元素有两种选择，一种只先留着，之后再配对。或者可以选择现在配对，限制就是当前这个元素的限制。由于最后的限制越来越小，因此我们显然尽可能带走 最大的几个。实际上是决策包容性的思想。 更小的元素显然可以替换一个 更大的元素并且仍然满足限制，但是反过来就不一定了（需要注意我们讨论的元素都是选择留给之后配对的元素，因此限制是更松的）。
但是问题是，我们何时选择配对，何时留着之后配对（之后可能有 更大的数来配对）？显然一个元素不可能一直留着，如果遍历到的元素限制已经小于留下来的 值了，那就无解了。但是留到最后，可供配对的元素就更多，更加有机会消掉更大的数。因此我们直接对于每个元素把决策推迟到不能再推为止，也就是之后元素的 值小于当前的 值时。这可以二分维护。
具体的，我们将所有元素按照 从大到小排序。对于每个元素，二分最后一个满足限制的 的位置，然后每个位置开一个 std::vector 记录一下，然后我们把当前元素加入一个按照 从大到小排的优先队列里。
然后我们从当前位置的 std::vector 里取出在这个时刻过期的元素（如果之前使用过了就跳过）。每次从优先队列里取出一个元素并弹出，如果使用过就继续取，直到取出两个合法的元素位置，配对扔到答案里，否则报告无解。
以上是算法的简要过程，下面是正确性证明。
首先我们构造的答案一定合法。当前优先队列里的元素一定满足 比当前位置大，并且 比当前位置的 要小。因此此时有最大的 的就是现在过期的这个元素，另外由于优先队列里的元素都排在前面，因此元素 值一定大于当前值，不会出现不合法的情况。
其次，不可能出现”报告无解，但是实际上有一组解的情况“。考虑使用归纳法。
我们只需要证明对于任意一个合法的解，我们都可以通过适当变换使其可以使用我们的算法构造出来。
对于 ，显然有唯一解。构造不出来就是无解了。
考虑 的情况。考虑最大值所在的一组。 我们的算法会选择 最大的元素 ，在 的元素中有最大和次大 值的元素配对，记作 。
如果这组解和 配对的恰好是 ，直接应用归纳假设即可。
否则，考虑和 配对的元素 ，这两个元素必然满足 这是因为我们的 在 的元素中具有最大和次大的 值，而和 配对则必须要满足这个限制。由于这两个元素有更小的 值，我们从后面 所在的组用 把这两个元素换出来并不会使限制更严格，这组解仍然满足条件，另外由于这些元素 已经大于 了，而 又是所有 中最大的，因此随便换肯定是满足限制的。
此时继续应用归纳假设即可。
证毕。
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
| #include <array>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
namespace solve {
struct solver {
struct elem {
uint val, limit, index;
};
uint n;
std::vector<std::array<uint, 3>> ans;
std::vector<elem> v;
std::vector<std::vector<uint>> deadline;
std::vector<bool> used;
void solve() {
for (size_t i = 0; i < n * 3; i++) {
std::cin >> v[i].val >> v[i].limit;
v[i].index = i;
}
std::sort(v.begin(), v.end(), [](const elem &lhs, const elem &rhs) {
return lhs.limit > rhs.limit;
});
std::vector<uint> val(n * 3);
for (size_t i = 0; i < n * 3; i++) {
val[i] = v[i].limit;
}
auto last_alive = [&](uint cur_val) {
return std::upper_bound(val.begin(), val.end(), cur_val,
std::greater<>()) -
val.begin() - 1;
};
std::priority_queue<std::pair<uint, uint>> pq;
for (uint i = 0; i < n * 3; i++) {
{
auto r = last_alive(v[i].val);
deadline[r].push_back(i);
pq.push({v[i].val, i});
}
for (auto &&j : deadline[i]) {
if (used[j]) {
continue;
}
ans.emplace_back();
ans.back()[0] = v[j].index;
used[j] = true;
for (size_t k = 1; k < 3; k++) {
while (true) {
if (pq.empty()) {
std::cout << "No\n";
return;
}
auto r = pq.top();
pq.pop();
if (used[r.second]) {
continue;
}
ans.back()[k] = v[r.second].index;
used[r.second] = true;
break;
}
}
}
}
std::cout << "Yes\n";
for (auto &&i : ans) {
for (size_t j = 0; j < 3; j++) {
std::cout << i[j] + 1 << " ";
}
std::cout << "\n";
}
}
solver(uint _n) : n(_n), ans(), v(n * 3), deadline(n * 3), used(3 * n) {
ans.reserve(n);
}
};
}
int main() {
uint t;
std::cin >> t;
while (t--) {
uint n;
std::cin >> n;
solve::solver slv(n);
slv.solve();
}
std::cout << std::flush;
return 0;
}
|