蒟蒻第一篇题解

传送门 P6607 [Code+#7]蚂蚁

• 首先，由于所有蚂蚁始终在运动且不会陷入死循环，因此所有蚂蚁都能爬到终点(也就是说题目的-1是拿来误导的)
• 接下来考虑穿过的情况,由于相遇会立刻反向，点与点之间的相对位置不变，可以看作存在一种特殊的”传递”(虽然时间不同所对的点也不同)
• example:(图丑不要在意)
  
  因此两点相遇前后一秒也可以看作两点相互穿过
• 综合起来可以发现，假如有一点向东(或西)走，且距离东(或西)x个单位，那么x个单位后必有一个点到达东边(或西边)端点。因此各个点的到达时间都可以确定，只需依次对应输出即可。
• 那么怎么对应呢？以第一个点为例，若向东走，则所需时间即为p[i]。若向西走，没有另一个向东走的点，则为l-p[i]；有点向东走的话，t即为p[向东走的第一个点]。
• 然后即可得出结论，若有向东走的点(a个),则前a个点所需时间以此为这些东走点的p,剩下n-a个点所需时间依次为剩下向西走的点的p。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,l,p[100005],dir[100005];
inline int read(){//可以跳过的快读 
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int main(){
	n=read();l=read();
	for(int i=1;i<=n;i++)
		p[i]=read();
	for(int i=1;i<=n;i++)
		dir[i]=read();
	for(int i=1;i<=n;i++)
		if(!dir[i])
			printf("%d ",p[i]);
	for(int i=1;i<=n;i++)
		if(dir[i])
			printf("%d ",l-p[i]);
	return 0;
}

---

add:这题和P1007 独木桥相似，AC完这题可以顺便过一下