$$\huge\color{blue}{坠落的蚂蚁\space |\space 贡献考虑}$$
题目大意
给定一根有限长度的木棍,上面有若干只运动的蚂蚁和一直不运动的蚂蚁$A$。运动的蚂蚁速度均为$1$。如果两只蚂蚁相遇了,那么他们将会调头并交换速度继续前行。如果有蚂蚁走到了$0$或$100$处,那么它们就掉下去了。请问初始时那只不运动的蚂蚁要几秒种后才会掉下去?
贡献分析
如果有除了$A$以外的两只蚂蚁相遇了,那么就相当于它们互相穿过了,对$A$的运动无贡献。下面是计算过程。
假设第一只蚂蚁速度为$v_1$,第二只蚂蚁速度为$v_2$。
那么相遇之后,第一只蚂蚁的速度变为了$v_2$,它现在的运动方向与之前的第二只蚂蚁相同。
那么就可以看做第二只蚂蚁从第一只蚂蚁身上穿过了。
同理,第一只蚂蚁也从第二只蚂蚁的身体里穿过了。
如果有运动的蚂蚁和$A$相遇了,那么$A$就继承了这只蚂蚁的速度和运动方向。某种意义上俩说,就相当于是$A$变成了那只蚂蚁。
相遇分析
有且仅有$A$左边往右走的蚂蚁和$A$右边往左走的蚂蚁是会和$A$相遇的。所以当$A$在初始情况时,在他左边往左走的、他右边往右走的蚂蚁都不用考虑。
于是我们只需要维护两个vector
,分别维护$A$左边往右走的蚂蚁和$A$右边往左走的蚂蚁即可。
综合计算
最简情况
如果在$A$左边往右走的蚂蚁有$1$只、在$A$右边往左走的蚂蚁也有$1$只。
假设在$A$左边往右走的蚂蚁先碰到$A$,那么$A$就往右边走了。
然后$A$和原来在$A$右边往左走的蚂蚁相遇了,所以$A$又往左走了。
接着它会碰到原来在$A$左边往右走的蚂蚁(此时它已经不动),所以这只蚂蚁不动了。
最后我们发现原来在$A$左边往右走的蚂蚁和在$A$右边往左走的蚂蚁都已经不会再和$A$相遇了,所以它们无贡献。
特殊情况
如果在$A$左边往右走的蚂蚁有$x$只、在$A$右边往左走的蚂蚁也有$x$只。
那么就相当于发生了$x$次最简情况!全部抵消掉。又只剩$A$自己这只蚂蚁了。
一般情况
在$A$左边往右走的蚂蚁有$x$只、在$A$右边往左走的蚂蚁有$y$只。
那么$A$会往蚂蚁多的那种位置爬。
即,如果$x$小于$y$,那么$A$最后会往左走,反之,(此时$x$大于$y$)最后$A$会往右走。
过渡问题
既然都知道怎么算了,那么现在最大的问题就是:
如何统计在$A$左边往右走的蚂蚁的数量和在$A$右边往左走的蚂蚁的数量。
预处理能贡献的对象
我们只需要建立三个vector
,其中两个记录能和$A$相遇的编号、另一个记录所有初始情况下在运动的蚂蚁的信息。
复杂度预估
由于上一部分的计算需要用到排序,所以总体复杂度为$O(nlog_2{n})$。
正解
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;//较高精度的浮点数
typedef pair<int,int> PII;
typedef pair<string,int> PSI;
vector<int> l,r;//保存A左边和右边的蚂蚁
vector<pair<int,int>> dat;//初始动的蚂蚁的信息
int A;//初始不动的蚂蚁
int main ()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n;
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
int id,p;
scanf("%d %d",&id,&p);
if (p==0)
A=id;
else
dat.push_back((PII){
id,p
});
}
sort(dat.begin(),dat.end());
for (auto i:dat)
{//注意只保存左边向右走、右边向左走的蚂蚁
if (i.first<A&&i.second==1)
l.push_back(i.first);//加入左边向右走的编号
if (i.first>A&&i.second==-1)
r.push_back(i.first);//加入右边向左走的编号
}
if (l.size()==r.size())
printf("Cannot fall!");//左边向右走和右边向左走的蚂蚁数量相同
//仍然会终止
if (l.size()>r.size())
printf("%d",100-l[l.size()-r.size()-1]);
if (l.size()<r.size())
printf("%d",r[l.size()]);
return 0;
}
作者:陆修远
链接:https://www.acwing.com/activity/content/code/content/3939585/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。