Java实现算法竞赛入门经典例题-蚂蚁

问题描述

一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米/秒。

当两只蚂蚁相撞时，二者同时掉头（掉头时间忽略不计）。

给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置。

输入格式

输入的第一行为数据组数。每组数据的第一行为3个正整数L, T, n（0≤n≤10 000）；以下n行每行描述一只蚂蚁的初始位置，

其中，整数x为蚂蚁距离木棍左端的距离（单位：厘米），字母表示初始朝向（L表示朝左，R表示朝右）。

输出格式

对于每组数据，输出n行，按输入顺序输出每只蚂蚁的位置和朝向（Turning表示正在碰撞）。

在第T秒之前已经掉下木棍的蚂蚁（正好爬到木棍边缘的不算）输出Fell off。

样例输入1

2

10 1 4

1 R

5 R

3 L

10 R

10 2 3

4 R

5 L

8 R

样例输出1

Case #1:

2 Turning

6 R

2 Turning

Fell off

Case #2:

3 L

6 R

10 R

PS：

当两只蚂蚁相撞我可以当作两只蚂蚁穿过去

虽然我再不停的转头，但是我的相对位置一直没变

我最开始掉下去得永远是最靠边得两只

package 第七次模拟;

import java.util.Arrays;

import java.util.Scanner;

public class Demo2蚂蚁 {

	public static class Node implements Comparable<Node> {

		int id;// 输入顺序

		int location;// -1,0,1

		int p;// 位置

		@Override

		public int compareTo(Node o) {

			// TODO 自动生成的方法存根

			if (this.p > o.p) {

				return 1;

			} else if (this.p < o.p) {

				return -1;

			}

			return 0;

		}

	}

	public static Node[] start;

	public static Node[] end;

	public static int[] order;

	public static String[] loca = { "L", "Turning", "R" };;

	public static void main(String[] args) {

		int num=1;

		Scanner sc = new Scanner(System.in);

		int count = sc.nextInt();

		while (count-- > 0) {

			int l = sc.nextInt();

			int t = sc.nextInt();

			int n = sc.nextInt();

			start = new Node[n];

			end = new Node[n];

			order = new int[n];

			for (int i = 0; i < n; i++) {

				start[i] = new Node();

				start[i].p = sc.nextInt();

				String c = sc.next();

				if (c.equals("L"))

					start[i].location = -1;

				else

					start[i].location = 1;

				start[i].id = i;

				end[i] = new Node();

				end[i].id = 0;

				end[i].p = start[i].p + t * start[i].location;

				end[i].location = start[i].location;

			}

			Arrays.sort(start);

			Arrays.sort(end);

			for (int j = 0; j < n; j++) {

				order[start[j].id] = j;

			}

			for (int j = 0; j < n - 1; j++) {

				if (end[j].p == end[j + 1].p) {

					end[j].location = 0;

					end[j + 1].location = 0;

				}

			}

			System.out.println("Case #"+ num++ +":");

			for (int i = 0; i < n; i++) {

				int temp = order[i];

				if (end[temp].p > l || end[temp].p < 0) {

					System.out.println("Fell off\n");

				} else {

					System.out.println(end[temp].p + " " + loca[end[temp].location + 1]);

				}

			}

		}

	}

}

巴特西

Java实现算法竞赛入门经典例题-蚂蚁

最新文章

热门文章