题意回顾

• 两个对向粒子加速器，距离 $L$
• $N$ 个 $x$ 粒子从位置 $0$ 出发，$N$ 个 $y$ 粒子从位置 $L$ 出发
• 每个粒子有发射时间 $t$ 和速度 $v$
• 粒子可以超越同种粒子
• $x$ 粒子和 $y$ 粒子相遇时湮灭
• 需要找出前 $K$ 次碰撞的粒子对

数据范围：$N \le 50000$，$K \le 100$

---

关键公式推导

1. 碰撞时间计算

设：

• $x$ 粒子 $i$：发射时间 $t_{x_i}$，速度 $v_{x_i}$
• $y$ 粒子 $j$：发射时间 $t_{y_j}$，速度 $v_{y_j}$

运动方程：

• $x$ 粒子：$pos_x(t) = v_{x_i} \cdot (t - t_{x_i})$
• $y$ 粒子：$pos_y(t) = L - v_{y_j} \cdot (t - t_{y_j})$

碰撞时 $pos_x(t) = pos_y(t)$： [ v_{x_i}(t - t_{x_i}) = L - v_{y_j}(t - t_{y_j}) ] 解得碰撞时间： [ t_c = \frac{L + v_{x_i}t_{x_i} + v_{y_j}t_{y_j}}{v_{x_i} + v_{y_j}} ] 条件：$t_c \ge \max(t_{x_i}, t_{y_j})$

---

算法思路

核心观察

由于 $K$ 很小（最多 100），我们不需要找出所有碰撞，只需要前 $K$ 次最早的碰撞。

这提示我们可以用**优先队列（堆）**来维护候选碰撞事件。

---

算法步骤

步骤 1：预处理排序

将 $x$ 粒子和 $y$ 粒子分别按速度排序：

• $x$ 粒子按 $v_x$ 升序排序
• $y$ 粒子按 $v_y$ 降序排序

这样排序后，对于每个 $x$ 粒子，与之碰撞时间较小的 $y$ 粒子会集中在某个区域。

步骤 2：为每个 $x$ 粒子找到候选 $y$ 粒子

对每个 $x$ 粒子 $i$，在 $y$ 粒子中找到一个可能最早碰撞的候选 $j$，将碰撞事件 $(t_c, i, j)$ 加入堆。

步骤 3：堆模拟碰撞过程

重复 $K$ 次：

1. 从堆中取出碰撞时间最小的事件 $(t_c, i, j)$
2. 输出这对粒子 $(i, j)$
3. 为 $x$ 粒子 $i$ 寻找下一个候选 $y$ 粒子，加入堆

---

高效寻找候选粒子

关键问题：如何快速找到每个 $x$ 粒子的下一个候选 $y$ 粒子？

方法：指针数组

对每个 $x$ 粒子 $i$，维护一个指针 $ptr[i]$，指向当前考虑的 $y$ 粒子索引。

初始时，为每个 $x$ 粒子设置 $ptr[i]$ 为某个合理的起始位置。

---

碰撞时间单调性

重要性质：对于固定的 $x$ 粒子 $i$，碰撞时间 $t_c$ 关于 $y$ 粒子索引在排序后是单谷函数（先递减后递增）。

因此我们可以用三分搜索找到最优的 $y$ 粒子。

---

完整算法实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 50005;

struct Particle {
    ll t, v;
    int id;
} x[MAXN], y[MAXN];

int N;
ll L;
int K;

// 计算碰撞时间
double collision_time(int i, int j) {
    return (L + x[i].v * x[i].t + y[j].v * y[j].t) * 1.0 / (x[i].v + y[j].v);
}

// 比较函数
bool cmp_x(Particle a, Particle b) {
    return a.v < b.v;  // x按速度升序
}

bool cmp_y(Particle a, Particle b) {
    return a.v > b.v;  // y按速度降序
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> L >> K;
    
    // 读入x粒子
    for (int i = 0; i < N; i++) {
        cin >> x[i].t >> x[i].v;
        x[i].id = i + 1;
    }
    
    // 读入y粒子
    for (int i = 0; i < N; i++) {
        cin >> y[i].t >> y[i].v;
        y[i].id = i + 1;
    }
    
    // 排序
    sort(x, x + N, cmp_x);
    sort(y, y + N, cmp_y);
    
    // 为每个x粒子找到初始候选y粒子（使用三分搜索）
    vector<int> best_j(N);
    for (int i = 0; i < N; i++) {
        int left = 0, right = N - 1;
        while (right - left > 10) {
            int mid1 = left + (right - left) / 3;
            int mid2 = right - (right - left) / 3;
            double t1 = collision_time(i, mid1);
            double t2 = collision_time(i, mid2);
            if (t1 < t2) {
                right = mid2 - 1;
            } else {
                left = mid1 + 1;
            }
        }
        
        // 在小区间内暴力找最优
        int best = left;
        double best_time = collision_time(i, left);
        for (int j = left + 1; j <= right; j++) {
            double t = collision_time(i, j);
            if (t < best_time) {
                best_time = t;
                best = j;
            }
        }
        best_j[i] = best;
    }
    
    // 优先队列维护候选碰撞
    using Event = tuple<double, int, int>;  // (碰撞时间, x索引, y索引)
    priority_queue<Event, vector<Event>, greater<Event>> pq;
    
    // 每个x粒子维护左右指针
    vector<int> left_ptr(N, 0), right_ptr(N, N - 1);
    
    // 初始加入每个x粒子的最佳候选
    for (int i = 0; i < N; i++) {
        if (best_j[i] >= 0 && best_j[i] < N) {
            double t = collision_time(i, best_j[i]);
            if (t >= max(x[i].t, y[best_j[i]].t)) {  // 满足时间条件
                pq.push({t, i, best_j[i]});
                // 标记这个y粒子已被这个x粒子考虑
                left_ptr[i] = right_ptr[i] = best_j[i];
            }
        }
    }
    
    // 处理前K次碰撞
    for (int k = 0; k < K; k++) {
        if (pq.empty()) break;
        
        auto [t_c, i, j] = pq.top();
        pq.pop();
        
        // 输出结果（注意输出的是原始编号）
        cout << x[i].id << " " << y[j].id << "\n";
        
        // 为x粒子i寻找新的候选y粒子
        // 尝试左边的y粒子
        if (left_ptr[i] > 0) {
            left_ptr[i]--;
            int new_j = left_ptr[i];
            double new_t = collision_time(i, new_j);
            if (new_t >= max(x[i].t, y[new_j].t)) {
                pq.push({new_t, i, new_j});
            }
        }
        
        // 尝试右边的y粒子
        if (right_ptr[i] < N - 1) {
            right_ptr[i]++;
            int new_j = right_ptr[i];
            double new_t = collision_time(i, new_j);
            if (new_t >= max(x[i].t, y[new_j].t)) {
                pq.push({new_t, i, new_j});
            }
        }
    }
    
    return 0;
}

---

算法优化

上面的实现可能会重复加入相同的碰撞事件。更精确的实现是：

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

struct Particle {
    ll t, v;
    int id;
};

int N;
ll L;
int K;

double collision_time(const Particle& x, const Particle& y) {
    return (L + x.v * x.t + y.v * y.t) * 1.0 / (x.v + y.v);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> L >> K;
    vector<Particle> x(N), y(N);
    
    for (int i = 0; i < N; i++) {
        cin >> x[i].t >> x[i].v;
        x[i].id = i + 1;
    }
    for (int i = 0; i < N; i++) {
        cin >> y[i].t >> y[i].v;
        y[i].id = i + 1;
    }
    
    // 排序
    sort(x.begin(), x.end(), [](auto a, auto b) { return a.v < b.v; });
    sort(y.begin(), y.end(), [](auto a, auto b) { return a.v > b.v; });
    
    // 对每个x粒子，找到使碰撞时间最小的y粒子区间
    vector<int> best_idx(N);
    for (int i = 0; i < N; i++) {
        int best = 0;
        double best_t = collision_time(x[i], y[0]);
        for (int j = 1; j < N; j++) {
            double t = collision_time(x[i], y[j]);
            if (t < best_t) {
                best_t = t;
                best = j;
            }
        }
        best_idx[i] = best;
    }
    
    // 优先队列 + 避免重复
    using Event = tuple<double, int, int>;
    priority_queue<Event, vector<Event>, greater<Event>> pq;
    vector<set<int>> used_y(N);  // 记录每个x粒子已使用的y索引
    
    for (int i = 0; i < N; i++) {
        int j = best_idx[i];
        double t = collision_time(x[i], y[j]);
        if (t >= max(x[i].t, y[j].t)) {
            pq.push({t, i, j});
            used_y[i].insert(j);
        }
    }
    
    for (int k = 0; k < K; k++) {
        if (pq.empty()) break;
        
        auto [t, i, j] = pq.top();
        pq.pop();
        
        cout << x[i].id << " " << y[j].id << "\n";
        
        // 加入相邻的候选
        for (int dj : {-1, 1}) {
            int new_j = j + dj;
            if (new_j >= 0 && new_j < N && !used_y[i].count(new_j)) {
                double new_t = collision_time(x[i], y[new_j]);
                if (new_t >= max(x[i].t, y[new_j].t)) {
                    pq.push({new_t, i, new_j});
                    used_y[i].insert(new_j);
                }
            }
        }
    }
    
    return 0;
}

---

复杂度分析

• 排序：$O(N \log N)$
• 寻找初始候选：$O(N^2)$ 最坏，但实际可以用更优方法优化到 $O(N \log N)$
• 堆操作：$O(K \log (NK))$

由于 $K \le 100$，实际运行效率可以接受。

---

总结

本题的关键在于：

1. 碰撞时间公式：$t_c = \frac{L + v_x t_x + v_y t_y}{v_x + v_y}$
2. 堆维护候选：利用 $K$ 小的特点，用优先队列维护最早碰撞
3. 排序优化：通过对粒子速度排序，使最优候选集中在局部
4. 避免重复：记录每个 $x$ 粒子已考虑的 $y$ 粒子