题解：区间匹配问题的贪心算法

---

问题分析

本题要求将 $n$ 个骑手两两配对，使得每对骑手的评分区间存在某种取值，使得评分之和等于 $s$。具体条件：

• 骑手 $i$ 的评分 $r_i \in [l_i, u_i]$
• 骑手 $i$ 和 $j$ 可以配对当且仅当存在 $r_i \in [l_i, u_i]$, $r_j \in [l_j, u_j]$ 使得 $r_i + r_j = s$

我们需要找出最大匹配（最多配对数）。

---

关键观察

1. 可配对条件等价转换

对于骑手 $i$ 和 $j$，他们可以配对的条件等价于：

$$[l_i, u_i] \cap [s - u_j, s - l_j] \neq \emptyset$$

即：

$$\max(l_i, s - u_j) \le \min(u_i, s - l_j)$$

这可以进一步简化为：

$$l_i \le s - l_j \quad \text{且} \quad u_i \ge s - u_j $$

或者更对称的形式：

$$l_i + l_j \le s \le u_i + u_j$$

2. 问题转化为区间匹配

将每个骑手 $i$ 视为两个关键值：

• 下界 $l_i$
• 上界 $u_i$

配对条件 $l_i + l_j \le s \le u_i + u_j$ 意味着：

• $l_i \le s - l_j$：骑手 $i$ 的下界不超过 $s$ 减去骑手 $j$ 的下界
• $u_i \ge s - u_j$：骑手 $i$ 的上界不低于 $s$ 减去骑手 $j$ 的上界

---

算法框架

第一步：排序处理

将所有骑手按上界 $u_i$ 从小到大排序。这样处理时，可以保证当前骑手 $i$ 的上界是当前最小的之一。

第二步：双指针扫描

维护两个指针：

• $i$：当前正在尝试匹配的骑手（从小到大扫描）
• $j$：从后向前扫描的指针，用于收集可能匹配的候选骑手

算法流程：

1. 从后向前找到第一个满足 $u_j + u_i \ge s$ 的骑手 $j$

   • 因为 $u_i$ 从小到大，当 $i$ 增大时，$u_j + u_i \ge s$ 的条件更容易满足
   • 所以 $j$ 指针可以单调向前移动

2. 将满足 $u_j + u_i \ge s$ 的骑手加入候选集合 cur

3. 在当前候选集合中寻找可以与骑手 $i$ 匹配的骑手：

   • 匹配条件：$l_i \le s - l_k$ 且 $u_i \ge s - u_k$
   • 由于 $u_i \ge s - u_k$ 已由加入条件保证，只需检查 $l_i \le s - l_k$
   • 即寻找 $l_k \le s - l_i$ 的骑手

4. 使用平衡树（set）维护候选集合，按 $l_k$ 排序，快速查找满足 $l_k \le s - l_i$ 的最大 $l_k$

第三步：贪心匹配

在候选集合中找到满足 $l_k \le s - l_i$ 的骑手 $k$：

• 如果存在，选择 $l_k$ 最大的骑手进行匹配（贪心策略）
• 这样可以留出更多"宽松"的骑手给后续匹配
• 匹配后从候选集合中删除该骑手

---

正确性证明

贪心策略的最优性

为什么选择 $l_k$ 最大的骑手进行匹配是最优的？

考虑当前骑手 $i$，候选集合中有多个骑手满足 $l_k \le s - l_i$。选择 $l_k$ 最大的骑手：

1. 保证了匹配的可行性
2. 留下 $l_k$ 较小的骑手，他们更可能满足后续骑手的 $l_i \le s - l_k$ 条件
3. 因为后续骑手的 $l_i$ 可能更大（由于按 $u_i$ 排序，$l_i$ 不一定单调，但整体趋势如此）

双指针维护候选集

由于骑手按 $u_i$ 排序，对于当前骑手 $i$，所有满足 $u_k + u_i \ge s$ 的骑手 $k$ 都来自 $i$ 之后的位置。随着 $i$ 增大，这个条件越来越容易满足，所以 $j$ 指针可以单调移动。

---

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 排序：$O(n \log n)$
  • 双指针扫描：$O(n)$
  • 平衡树操作：每次插入、查找、删除 $O(\log n)$，总 $O(n \log n)$
• 空间复杂度：$O(n)$

对于 $n \le 2\times 10^5$ 完全可行。

---

算法步骤

1. 输入与预处理：

   • 读取 $n, s$
   • 读取每个骑手的 $[l_i, u_i]$，存储为 $(l_i, u_i, id)$
   • 按 $u_i$ 从小到大排序

2. 双指针扫描：

#include <bits/stdc++.h>
using namespace std;

struct Rider {
    long long l, u, id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    long long n, s;
    cin >> n >> s;
    
    vector<Rider> riders(n);
    for (int i = 0; i < n; i++) {
        cin >> riders[i].l >> riders[i].u;
        riders[i].id = i + 1;
    }
    
    // 按u从小到大排序
    sort(riders.begin(), riders.end(), [](const Rider& a, const Rider& b) {
        return a.u < b.u;
    });
    
    vector<bool> matched(n, false);
    vector<pair<int, int>> matches;
    
    // 用于按l排序的集合
    set<pair<long long, int>> cur; // (l, index)
    
    int j = n - 1;
    for (int i = 0; i < n; i++) {
        if (matched[i]) continue;
        
        // 扩展候选集：添加所有满足 u_j + u_i >= s 的骑手
        while (j > i && riders[j].u + riders[i].u >= s) {
            if (!matched[j]) {
                cur.insert({riders[j].l, j});
            }
            j--;
        }
        
        // 在候选集中查找匹配：l_k <= s - l_i 的最大 l_k
        auto it = cur.lower_bound({s - riders[i].l + 1, 0});
        if (it != cur.begin()) {
            it--; // 找到满足条件的最大l_k
            int k = it->second;
            
            // 匹配骑手i和骑手k
            matches.push_back({riders[i].id, riders[k].id});
            matched[i] = matched[k] = true;
            cur.erase(it);
        }
    }
    
    // 输出结果
    cout << matches.size() << "\n";
    for (auto& match : matches) {
        cout << match.first << " " << match.second << "\n";
    }
    
    return 0;
}

3. 输出结果：
   • 输出匹配对数
   • 输出每对匹配的骑手编号

---

总结

本题是一道区间匹配与贪心算法的综合题目，主要考察：

1. 条件转化能力：将复杂的区间存在性条件转化为简单的不等式
2. 排序技巧：通过巧妙的排序简化问题结构
3. 双指针维护：高效维护候选匹配集合
4. 贪心策略设计：选择最优匹配对象以最大化匹配数

算法的核心在于：

• 将配对条件简化为 $l_i + l_j \le s \le u_i + u_j$
• 按 $u_i$ 排序后，使用双指针维护候选集
• 在候选集中贪心地选择 $l_k$ 最大的骑手匹配

这种"排序+双指针+贪心选择"的方法是解决区间匹配问题的经典范式，在保证正确性的同时达到了高效的时间复杂度。