思维题 UVA 10881 Piotr's Ants

题目传送门

 /*
题意:在坐标轴上一群蚂蚁向左或向右爬,问经过ts后,蚂蚁的位置和状态
思维题:本题的关键1:蚂蚁相撞看作是对穿过去,那么只要判断谁是谁就可以了
关键2:蚂蚁的相对位置不变 关键3:order数组记录顺序
*/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std; const int MAXN = 1e4 + ;
const int INF = 0x3f3f3f3f;
const char dir_name[][] = {"L", "Turning", "R"};
struct Ant
{
int pos, dir, id;
bool operator < (const Ant &a) const
{
return pos < a.pos;
}
}pre[MAXN], now[MAXN];
int order[MAXN]; int main(void) //UVA 10881 Piotr's Ants
{
// freopen ("UVA_10881.in", "r", stdin); int T; int cas = ; int len, t, n;
scanf ("%d", &T);
while (T--)
{
scanf ("%d%d%d", &len, &t, &n);
char ch;
for (int i=; i<=n; ++i)
{
int p, d; char ch;
scanf ("%d %c", &p, &ch);
d = ((ch=='L') ? - : );
pre[i] = (Ant) {p, d, i};
now[i] = (Ant) {p+t*d, d, };
} sort (pre+, pre++n); //计算相对位置
for (int i=; i<=n; ++i) order[pre[i].id] = i; //输入(输出)的顺序 sort (now+, now++n);
for (int i=; i<n; ++i)
{
if (now[i].pos == now[i+].pos)
now[i].dir = now[i+].dir = ;
} printf ("Case #%d:\n", ++cas);
for (int i=; i<=n; ++i)
{
int x = order[i];
if (now[x].pos < || now[x].pos > len) puts ("Fell off");
else
{
printf ("%d %s\n", now[x].pos, dir_name[now[x].dir+]);
}
} puts ("");
} return ;
} /*
Case #1:
2 Turning
6 R
2 Turning
Fell off Case #2:
3 L
6 R
10 R
*/
上一篇:loadrunner 利用JDBC操作mysql数据库


下一篇:POJ 1852 Ants || UVA 10881 - Piotr's Ants 经典的蚂蚁问题