UVA10881 Piotr's Ants 思维题

链接

这个题其实不难做，关键是发散思维。

经过长时间的观察后，我们发现两个结论：

• 每个蚂蚁的相对位置不变。
• 相遇后反向可以看做不反向直接走。

第二个结论我们用来判断蚂蚁的位置，然后用第一个结论我们来判断蚂蚁的编号。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 10010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

struct Ants{
    int posi,id;
    char chao;
    inline bool operator < (const Ants &b)const{
        return posi<b.posi;
    }
};
Ants a[N],b[N],ans[N];

int t,l,times,n;

inline char GetChar(){
    char c=getchar();
    while(c!='L'&&c!='R') c=getchar();
    return c;
}

int main(){
    freopen("my.in","r",stdin);
    freopen("my.out","w",stdout);
    read(t);
    for(int q=1;q<=t;q++){
        read(l);read(times);read(n);
        for(int i=1;i<=n;i++){
            read(a[i].posi);a[i].id=i;
            a[i].chao=GetChar();
            b[i]=a[i];
            if(a[i].chao=='L') a[i].posi-=times;
            else a[i].posi+=times;
        }
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        a[0].posi=-INF;a[n+1].posi=INF;
        for(int i=1;i<=n;i++){
            if(a[i].posi<0||a[i].posi>l) a[i].chao='F';
            else if(a[i].posi==a[i-1].posi||a[i].posi==a[i+1].posi) a[i].chao='T';
        }
        for(int i=1;i<=n;i++){
            ans[b[i].id]=a[i];
        }
        printf("Case #%d:
",q);
        for(int i=1;i<=n;i++){
            if(ans[i].chao=='F') printf("Fell off");
            else if(ans[i].chao=='T') printf("%d Turning",ans[i].posi);
            else printf("%d %c",ans[i].posi,ans[i].chao);
            putchar('
'); 
        }
        printf("
");
    }
    return 0;
}