2021ICPC新疆省赛——F题 chino with ball

CF题目链接
看着非常复杂的一道物理模拟题，做复现的时候也是往复杂了去想，如何模拟小球的运动之类的，赛后看题解才知道这题的做法非常简单，但是要想到这个做法还是有点困难的。

核心思想：小球碰撞就交换速度，其实就等价于小球互相穿过继续运动。

所以这个问题就可以被简化成将所有小球的初始位置加上速度x运动时间，然后排序输出即可。注意输出顺序要对应小球的编号。

代码：

#include 
const long long N = 1e5 + 5;
using namespace std;

struct ball //记录原始的小球
{
    long long pos, idx;
} b[N];
bool operator<(ball a, ball b) { return a.pos < b.pos; }
long long pos[N], ans[N];

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    long long n, t, v;
    cin >> n >> t;
    for (long long i = 0; i < n; i++)
    {
        b[i].idx = i;
        cin >> b[i].pos >> v;
        pos[i] = b[i].pos + v * t; //记录所有小球运动后的位置
    }
    sort(b, b + n);
    sort(pos, pos + n);
    for (long long i = 0; i < n; i++) //得到输出的顺序
        ans[b[i].idx] = pos[i];
    for (long long i = 0; i < n; i++)
    {
        cout << ans[i];
        if (i != n - 1)
            cout << " ";
        else
            cout << "n";
    }
    return 0;
}