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;
}