首页 > ACM题库 > UVA > Uva-10881-Piotr’s Ants[经典模拟]
2014
02-26

Uva-10881-Piotr’s Ants[经典模拟]

Piotr’s Ants

Piotr likes playing with ants. He has n of them on a horizontal pole L cm long. Each ant is facing either left or right and walks at a constant speed of 1 cm/s. When two ants bump into each other, they both turn around (instantaneously) and start walking in opposite directions. Piotr knows where each of the ants starts and which direction it is facing and wants to calculate where the ants will end up T seconds from now.

Input
The first line of input gives the number of cases, NN test cases follow. Each one starts with a line containing 3 integers: L , T and n (0 <= n <= 10000) . The next n lines give the locations of the n ants (measured in cm from the left end of the pole) and the direction they are facing (L or R).

Output
For each test case, output one line containing “Case #x:” followed by n lines describing the locations and directions of the n ants in the same format and order as in the input. If two or more ants are at the same location, print “Turning” instead of “L” or “R” for their direction. If an ant falls off the pole beforeT seconds, print “Fell off” for that ant. Print an empty line after each test case.

Sample Input

2
10 1 4
1 R
5 R
3 L
10 R
10 2 3
4 R
5 L
8 R

Sample Output

Case #1:
2 Turning
6 R
2 Turning
Fell off

Case #2:
3 L
6 R
10 R

 

题目大意:一根长L厘米的木棍上有n只蚂蚁,每只蚂蚁有个开始的位置和爬行方向,速度为1.当两只蚂蚁相撞后,两者同时掉头继续爬行,求按输入顺序给出每只蚂蚁T秒后的位置后朝向。

解题思路:

1. 每只蚂蚁相撞后同时掉头可以看做对穿而过,关键的问题就在于求位置的变化。

2.按位置从小到大排序,可以惊奇的发现排序后(befor数组和after数组)所有的蚂蚁相对位置并没有变化,改变的只是朝向。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn=10005;

struct node
{
    int   id, p, d;   //d表示朝向,-1表示左,0表示碰撞中,1表示右。
    bool operator < (const node& S)const
    {
        return p<S.p;
    }
} befor[maxn],after[maxn];

char dirname[][10]={"L","Turning","R"};
int  order[maxn];

int main()
{
    int  T, n, L, t, tcase=0;
    int  ss[10005];
    cin >> T;
    while(T--)
    {
        scanf("%d%d%d",&L, &t, &n);
        printf("Case #%d:\n",++tcase);
        for(int i=0; i<n; i++)
        {
            int  p, d;
            char c;
            scanf("%d %c",&p,&c);
            d=(c=='L'?-1:1);
            befor[i]=(node){i,p,d};
            after[i]=(node){0,p+t*d,d};  //所以的蚂蚁相撞后可以看做对穿而过
        }
        sort(befor,befor+n);
        for(int i=0; i<n; i++)  //最巧妙的地方在这里,第一次从左到右所有的蚂蚁的相对位置没有变化
            order[befor[i].id]=i;
        sort(after,after+n);
        for(int i=0; i<n-1; i++)
            if(after[i].p==after[i+1].p)  after[i].d=after[i+1].d=0;
        for(int i=0; i<n; i++)
        {
            int a=order[i];
            if(after[a].p>=0&&after[a].p<=L)
            {
                printf("%d %s\n",after[a].p,dirname[after[a].d+1]);
            }
            else
                printf("Fell off\n");
        }
        puts("");
    }
    return 0;
}

  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  3. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?

  4. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;