Bessie 与 Elsie 各有 $n$ 张饼，每人对自己与对方的饼均有打分。Bessie 首先给 Essie 一张饼，此后 Essie 按自己的打分回赠，给出饼分值不小于收到饼，但差在 $d$ 以内。此后 Bessie 再回赠，如此直至一方收到其打分为 0 的饼。当 Bessie 的每张饼作为第一张饼，输出最小交换次数。如一方无法按条件给出饼，报错。
由于要求每一起点的最小步数，本问题类似最短路，而最小步数的要求恰能排除状态中其他饼是否用过之信息——一旦可用，则已经用过。但直接以最短路建图求解效率为 $text(O)(n^2)$，因 $d$ 可能接近 $n$ 使饼间需要两两连边（由于边长均为 1，最短路可采用搜索 $text(O)(n)$ 完成）。
解决区间连边一般用线段树优化建图：为 $2n$ 长总区间建线段树，连边时在线段树表示并连边，如此一个区间只需连 $text(O)(log n)$ 条，图大小及效率为 $text(O)(n log n)$。但我更想练习 STL，因此选择 STL 解决。为双方各建一个 std::set，BFS 时在对方饼中查找 $[k,k+d]$ 范围内饼，入队后即从 std::set 内删除。由于 std::set 查找与迭代操作均为 $text(O)(log n)$，且每张饼仅出现一次，总时间为 $text(O)(n log n)$。
#include <cstring>
#include <iostream>
#include <set>
#include <queue>
#define F(var, start, end) for\
(int var = (start), var##_done = (end); var <= var##_done; ++var)
const int oxis = 200003;
int score_self[oxis], // 制作饼的一方认为的美味度
score_other[oxis], // 对方认为的美味度
ans[oxis]; // 最小深度，即答案
// 使 std::set 中按对方认为的美味度排序，从而可以查找
struct compare {
bool operator()(const int &u, const int &v) const {
return score_other[u] != score_other[v] ?
score_other[u] < score_other[v] : u < v;
}
};
int main()
{
std::ios::sync_with_stdio(false);
int n, d;
std::cin >> n >> d;
memset(ans, 127, sizeof(ans));
std::set<int, compare> bessie, elsie; // bessie 存 bessie 收到的饼
std::queue<int> bfs;
F (i, 1, n) {
std::cin >> score_self[i] >> score_other[i];
elsie.insert(i);
}
F (i, 1 + n, 2 * n) {
std::cin >> score_other[i] >> score_self[i];
bessie.insert(i);
}
F (i, 1, 2 * n)
if (score_other[i] == 0) {
bfs.push(i);
ans[i] = 1;
std::set<int, compare> &cow = i > n ? bessie : elsie;
cow.erase(i);
}
while (!bfs.empty()) {
int now = bfs.front();
bfs.pop();
int tastiness = score_self[now], depth = 1 + ans[now];
std::set<int, compare> &cow = now > n ? elsie : bessie;
// 收到饼的美味度 >= 给出饼的美味度 - d
// 将下界放到 score_other[0] 以利用 lower_bound
*score_other = tastiness - d;
for (auto i = cow.lower_bound(0);
i != cow.end() && score_other[*i] <= tastiness;
cow.erase(i++)) {
int received = *i;
bfs.push(received);
ans[received] = depth;
}
}
F (i, 1, n)
if (ans[i] == 2139062143)
std::cout << "-1\n";
else
std::cout << ans[i] << '\n';
}