思维题, 解释起来挺抽象的, 要有一定的脑中模拟能力
关键规则
如果两只蚂蚁碰头,则它们立即交换速度并继续爬动。
对于除A外的蚂蚁, 除A之外的所有蚂蚁都是在运动着的, 当两只蚂蚁碰头后掉头, 相当于nothing happened, 因为这两只蚂蚁只是交换了一下, 对于A并没有什么不同, 因此将它们看成直接穿过对方
这样问题就简化了许多, 对于两类蚂蚁:在A左边而往左走、在A右边而往右走, 它们不会与A碰头, 而是一直向前走直到掉下去。
所以在接下来的问题中我们可以剔除这两种蚂蚁, 场上只剩下另外两种蚂蚁: 在A左边向右走, 在A右边向左走, 这两种蚂蚁是会与A碰头的。
对于A与其它蚂蚁碰头, A每与其它蚂蚁碰一次头, A就会改变一次方向,
- 当左边和右边蚂蚁数量相等时, 左右影响抵消, A最终会静止。
- 当左边和右边蚂蚁数量不等时,A的方向与蚂蚁更多的方向相等. 至于A的路程要找到较少边蚂蚁被全部抵消后A碰到的较多边第一只蚂蚁, 坠落时间即为此蚂蚁无阻碍走完全程所需要的时间
多想想就明白了, 没有图只能尬讲
说这么多不如举例来得实在
对于如下样例
4
10 1
90 0
95 -1
98 -1
可以看到蚂蚁全部为有效蚂蚁, A为90
把它们放到数轴上
10 90 95 98
左边的个数为1, 右边的个数为2, 所以10与95抵消, 抵消后A第一个碰到的蚂蚁是98, A与98号蚂蚁碰头后A的状态将不再改变, A会代替98走完剩下的路程;而98蚂蚁在与A碰头前是一直往前走的, 所以答案即为98号蚂蚁无阻碍的走完全程的时间:98
AC代码(含注释)
//
// Created by trudbot on 2022/7/28.
//
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, A; cin >> n;
vector<int> l, r;//保存有效的左边的蚂蚁和右边的蚂蚁的位置
vector<pair<int, int>> data;//用pair来保存蚂蚁的位置和方向
while(n --)
{
int x, y; cin >> x >> y;
if(y == 0) A = x;//找一下A
else data.push_back({x, y});
}
//排个序像数轴那样放好, 目的是使 l 和 r是有序的
sort(data.begin(), data.end());
for(auto i : data)
{
//只保存两种蚂蚁, 左边向右走 和 右边向左走
if(i.first < A && i.second == 1) l.push_back(i.first);
else if(i.first > A && i.second == -1) r.push_back(i.first);
}
//左右蚂蚁相等, 最终A仍会静止
if(l.size() == r.size()) cout << "Cannot fall!";
//左边更多时, 左边的后r.size个蚂蚁被右边抵消
else if(l.size() > r.size()) cout << 100 - l[l.size()-r.size()-1];
//右边更多时, 右边前l.size个蚂蚁被左边抵消
else cout << r[l.size()];
return 0;
}
$dalao$,为什么要排序?不排序不是也可以获取左侧方向向右的与右侧方向向左的蚂蚁吗
因为 L 和 R是要求有序的, 抵消的时候要两边最靠近A的抵消。 这里也可以获取完L和R后再对它们排序
这题我选择放弃
我帮您补充了一下?
补充
🥰
学到了
100 - l[l.size()-r.size()-1];有个小疑问,这个为什么要减一
数组的末尾去掉n个元素后, 最后一个元素的下标就是 len - n - 1嘛
谢谢大佬,豁然开朗
tql
大哥这个思路太妙了
在A左边向左走,在A右边向右走也是可以碰头的
非A的蚂蚁之间碰头后没有任何的影响, 所以认为非A蚂蚁遇到后不会交换速度, 而是继续走
是的,直接模拟也可以做,最多100秒掉下去,每次走0.5秒判断下,不过写着麻烦
模拟就太麻烦了, 要维护这么多的点
我就是这样写的 哈哈还好