P6607 [Code+#7]蚂蚁

Coros_Trusds · 2021-08-23 14:57:59 · 题解

更好的阅读体验

\mathsf{Title\space Describe.}

在东西排布的两棵树之间悬挂着一条长为 L 的细绳，有 N 只蚂蚁在这条绳上。这些蚂蚁希望通过绳子爬到任何一棵树上，但这条绳太细了，导致两只蚂蚁不能并排爬行，也不能交错而过。

它们想到了一个方法：每只蚂蚁都以每单位时间移动一个单位距离的速度不断向前爬，当迎面碰到另一只蚂蚁时，两只蚂蚁都将立即掉头并继续向前爬。现在，蚂蚁们想知道自己是否能爬下绳子，如果能，它们还希望知道自己爬下绳子所花的时间。为了方便，我们按初始时位置从东到西的顺序对蚂蚁从 1 开始编号。

\mathsf{Analytical\space thinking.}

遇到这种模拟题，千万不能具体地去处理对待，一定要从总体去看待题目。

比方说这道题，我最初的思路是一只只的蚂蚁地去处理每只蚂蚁，想了个 O(n^2) 的思路，但是 1\le n\le10^5，显然不能在 1 秒内通过。

然后我就想啊：

先考虑极端情况：有 10^5 只蚂蚁，这么多蚂蚁，如果一只只去看是在是不科学，如果一只蚂蚁朝向东边，那么直接让它走过去好了——但是如果在它的东边还有蚂蚁怎么办呢？哦，对了，如果遇到的话，那么可以看成是穿过去了（双双掉头就相当于传过去），那就先让朝向东边的蚂蚁走过去，然后我再让这些朝西边的蚂蚁往左边走不就好了？

\mathsf{Code.}

//2021/8/23

#include <iostream>

#include <cstdio>

#define debug(c) cerr<<#c<<" = "<<c<<endl

namespace Newstd
{
    inline int read()
    {
        int x=0,f=1;char ch=getchar();
        while(ch<'0' || ch>'9')
        {
            if(ch=='-')f=-1;
            ch=getchar();
        }

        while(ch>='0' && ch<='9')
        {
            x=x*10+ch-'0';ch=getchar();
        }
        return x*f;
    }
    inline void print(int x)
    {
        if(x<0)
        {
            putchar('-');x=-x;
        }
        if(x>9)
        {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}

using namespace Newstd;

using namespace std;

const int ma=100005;

int a[ma],st[ma];

int n,l;

int main(void)
{
    scanf("%d%d",&n,&l);

    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&st[i]);
    }

    for(register int i=1;i<=n;i++)
    {
        if(st[i]==false)
        {
            printf("%d ",a[i]);
        }
    }

    //这里要保证面向东边的蚂蚁首先到达，所以分成两个循环

    for(register int i=1;i<=n;i++)
    {
        if(st[i]==true)
        {
            printf("%d ",l-a[i]);
        }
    }

    return 0;
}