UVa 19299 - Piotr's Ants

传送门

UVa 19299 - Piotr’s Ants

题意

有几只蚂蚁在木板上,如果碰到会转向,求各自在T秒后的位置和方向

思路

大白例题,不会做,不过边看分析边想倒挺有意思的。

每只蚂蚁的相对位置前后都不会改变。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 10000 + 5;
const int INF = 0x3f3f3f3f;
const char dirName[][40] = {"L", "Turning", "R"};
 
struct ANT
{
    int id, p, d;
    bool operator < (const ANT &a) const
    {
        return p < a.p;
    }
}bef[MAXN], aft[MAXN];
 
int order[MAXN];
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int T, i, j, t, n, len, p, d, cases = 0;
    char ch;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &len, &t, &n);
        for (i = 0; i < n; i++)
        {
            scanf("%d %c", &p, &ch);
            d = (ch == 'L' ? -1 : 1);
            bef[i] = (ANT) {i, p, d};
            aft[i] = (ANT) {0, p + t * d, d};
        }
        sort(bef, bef + n);
        for (i = 0; i < n; i++)
            order[bef[i].id] = i;
        sort(aft, aft + n);
        for (i = 0; i < n - 1; i++)
            if (aft[i].p == aft[i + 1].p)
                aft[i].d = aft[i + 1].d = 0;
        printf("Case #%d:\n", ++cases);
        for (i = 0; i < n; i++)
        {
            int a = order[i];
            if (aft[a].p < 0 || aft[a].p > len)
                printf("Fell off\n");
            else
                printf("%d %s\n", aft[a].p, dirName[aft[a].d + 1]);
        }
        puts("");
    }
    return 0;
}

Powered by Jekyll and Theme by solid