KY89 坠落的蚂蚁

这个题目用暴力模拟死路一条。。。

Theramenes大佬的思路真是牛b！（坠落的蚂蚁__牛客网 (nowcoder.com) ）      

简单提炼一下就是：

设整条木棍上共有N只蚂蚁，有n只向左，1只不会动的蚂蚁，m只向右，根据设定，蚂蚁相遇会换速度（矢量），即每一次相遇，都有两只蚂蚁交换阵营（三只相遇可视为两次相遇）。但因速度大小一致，即使改变了方向，两者的左右相对位置仍不会发生改变，这就是蚂蚁的相对位置永远不变的含义。

不难看出，相遇发生的改变并不会影响 “整条木棍上共有N只蚂蚁，有n只向左，1只不会动的蚂蚁，m只向右” 这一设定，则经过无限时间后，结果只有一个，就是有n只蚂蚁向左掉落，1只蚂蚁孤零零在棍上，m只蚂蚁向右掉落。

关于如何确定蚂蚁A掉落时间这个问题，结论是：

情况一：蚂蚁A左边的蚂蚁数量小于向左走的蚂蚁数量时，蚂蚁A（初始状态从左到右相对位置为k）的掉落时间等于初始状态下向左走的第k只蚂蚁在不发生相遇情况下的掉落时间。

情况二：蚂蚁A左边的蚂蚁数量等于向左走的蚂蚁数量时，不发生掉落。

情况三：蚂蚁A左边的蚂蚁数量大于向左走的蚂蚁数量时，蚂蚁A（初始状态从右到左相对位置为k’ = N-k+1）的掉落时间等于初始状态下向右走的第k只蚂蚁在不发生相遇情况下的掉落时间。

上面的结论可以用数学证明，但挺麻烦的，用一个巧妙的设想来理解这个结论，我们设想两蚂蚁相遇交换的不止是速度，更是他们的使命（向着初始方向到达端点），那么我们可以认为初始状态下某只蚂蚁的使命一直在执行，只不过途中可能会交由给另一只蚂蚁来执行。而根据蚂蚁的相对位置永远不变这一前提，在情况一下，蚂蚁A最终行使的是初始状态下向左走的第k只蚂蚁的使命，即第k个向左到达端点。其他情况同理。

实在理解不了就当数学结论记着吧  >.<

#include
#include
#include
using namespace std;struct ant{int position;int direction;bool operator < (const ant &a) const{return position < a.position;}
};int main(){int N;cin >> N;vector ants(N);for(int i = 0; i < N; i++){cin >> ants[i].position >> ants[i].direction;}sort(ants.begin(), ants.end());int k,leftnum, toleft = 0;for(int i = 0; i < N; i++){if(ants[i].direction == -1) toleft++;if(ants[i].direction == 0){k = i + 1;    //i从0开始编号，而相对位置从1开始编号，需要修正+1leftnum = i;    //此处是修正后的表示，原表示应为i-1+1} }bool flag = true;int ans = 0;if(leftnum < toleft){    //情况一int cnt = 0;for(int i = 0; i < N; i++){if(ants[i].direction == -1) cnt++;if(cnt == k){     ans = ants[i].position;break;} }}else if(leftnum == toleft) flag = false;  //情况二else{    //情况三int cnt = 0;for(int i = N-1; i>=0; i--){if(ants[i].direction == 1) cnt++;if(cnt == N-k+1) {ans = 100 - ants[i].position;break;}}}if(flag) cout << ans <

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！