比赛链接

2025牛客寒假算法基础集训营3

E.智乃的小球

题目描述

在一水平光滑平面上，有 𝑛 个质量相同，体积可忽略不计的小球。所有小球位于同一条直线上，并且它们的初始速度 𝑣0 要么为 −1 m/s，要么为 1 m/s。初始速度为 −1 表示小球沿直线方向向左，初始速度为 1 表示小球的初速度沿直线向右。

请不要担心，本题并非一道物理学问题。你只需要知道当两个质量完全相同的物体发生碰撞时，它们将彼此交换互相的速度。

现在智乃想要知道，经过足够长的时间后，是否会发生第 𝑘 对碰撞关系，以及从初始时刻开始，经过多长时间后发生第 𝑘 对小球之间的碰撞（同一时刻可能会发生多对碰撞，但在任意一个碰撞关系中仅涉及到两个小球）。

解题思路

1. 按方向分类存储小球；
2. 排序数组；
3. 计算碰撞次数 k ；

• 如果碰撞次数 < k ：输出答案；
• 否则：二分答案。

完整代码

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

typedef long long ll;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> R, L;
    for (int i = 0; i < n; ++i) {
        int p, v;
        scanf("%d%d", &p, &v);
        if (v == 1) {
            R.push_back(p);
        } else {
            L.push_back(p);
        }
    }
    sort(R.begin(), R.end());
    sort(L.begin(), L.end());
    
    ll m = 0;
    if (R.size() <= L.size()) {
        for (int r : R) {
            auto it = upper_bound(L.begin(), L.end(), r);
            m += L.end() - it;
        }
    } else {
        for (int l : L) {
            auto it = upper_bound(R.begin(), R.end(), l);
            m += it - R.begin();
        }
    }
    if (m < k) {
        printf("No\n");
        return 0;
    }
    
    ll low = 0, high = 2e18;
    while (low < high) {
        ll mid = (low + high) / 2;
        ll cnt = 0;
        if (R.size() <= L.size()) {
            for (int r : R) {
                auto it_left = upper_bound(L.begin(), L.end(), r);
                int left = it_left - L.begin();
                ll max_p = r + mid;
                auto it_right = upper_bound(L.begin(), L.end(), max_p);
                int right = (it_right - L.begin()) - 1;
                if (right >= left) {
                    cnt += right - left + 1;
                }
            }
        } else {
            for (int l : L) {
                ll min_p = l - mid;
                auto it_left = lower_bound(R.begin(), R.end(), min_p);
                auto it_right = upper_bound(R.begin(), R.end(), l - 1);
                cnt += it_right - it_left;
            }
        }
        if (cnt >= k) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    double ans = low / 2.0;
    printf("Yes\n%.6lf\n", ans);
    return 0;
}

如有错误欢迎指正~