Powered by:NEFU AB-IN

Link

3474. 坠落的蚂蚁

• 题意

  一根长度为 1 米的木棒上有若干只蚂蚁在爬动。
  它们的速度为每秒一厘米或静止不动，方向只有两种，向左或者向右。
  如果两只蚂蚁碰头，则它们立即交换速度并继续爬动。
  三只蚂蚁碰头，则两边的蚂蚁交换速度，中间的蚂蚁仍然静止。
  如果它们爬到了木棒的边缘（0 或 100 厘米处）则会从木棒上坠落下去。
  在某一时刻蚂蚁的位置各不相同且均在整数厘米处（即 1，2，3，…99 厘米），有且只有一只蚂蚁 A 速度为 0，其他蚂蚁均在向左或向右爬动。
  给出该时刻木棒上的所有蚂蚁位置和初始速度，找出蚂蚁 A 从此时刻到坠落所需要的时间。

• 思路

  对于除A外的蚂蚁， 除A之外的所有蚂蚁都是在运动着的，而且速度相同，只是方向不同

  两只蚂蚁碰头后掉头 等价于 直接穿过对方 （因为对于A来说并无不同）

  这样问题就简化了许多, 对于两类蚂蚁:

  • 在A左边而往左走
  • 在A右边而往右走
  • 它们不会与A碰头，而是一直向前走直到掉下去。

  所以在接下来的问题中我们可以剔除这两种蚂蚁和A， 场上只剩下另外两种蚂蚁：

  • 在A左边向右走
  • 在A右边向左走
  • 这两种蚂蚁是会与A碰头的。

  对于A与其它蚂蚁碰头， A每与其它蚂蚁碰一次头， A就会改变一次方向，
  所以

  • 当左边和右边蚂蚁数量相等时， 左右影响抵消， A最终会静止。
  • 当左边和右边蚂蚁数量不等时，A的方向与蚂蚁更多的方向相等. 至于A的路程要找到较少边蚂蚁被全部抵消后A碰到的较多边第一只蚂蚁, 坠落时间即为此蚂蚁无阻碍走完全程所需要的时间

• 代码

/*
 * @Author: NEFU AB-IN
 * @Date: 2022-08-16 15:47:06
 * @FilePath: \Acwing\3474\3474.cpp
 * @LastEditTime: 2022-08-16 16:05:17
 */
#include 
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

signed main()
{
    IOS;
    int n;
    cin >> n;
    vector<PII> a(N);
    int A;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].first >> a[i].second;
        if (!a[i].second)
            A = a[i].first;
    }
    sort(a.begin(), a.end());
    vector<int> l, r;
    for (auto [pos, v] : a)
    {
        // 排除掉一些点
        if (v == 0 || (pos < A && v < 0) || (pos > A && v > 0))
            continue;
        if (pos < A)
            l.push_back(pos);
        else
            r.push_back(pos);
    }
    //左右蚂蚁相等, 最终A仍会静止
    if (SZ(l) == SZ(r))
        cout << "Cannot fall!";
    //左边更多时, 左边的后r.size个蚂蚁被右边抵消
    else if (SZ(l) > SZ(r))
        cout << 100 - l[SZ(l) - SZ(r) - 1];
    //右边更多时, 右边前l.size个蚂蚁被左边抵消
    else
        cout << r[SZ(l)];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54