[CCF CSP] 201803-2 碰撞的小球

12/16

19:34

题目描述

数轴上有一条长度为L（L为偶数)的线段，左端点在原点，右端点在坐标L处。有n个不计体积的小球在线段上，开始时所有的小球都处在偶数坐标上，速度方向向右，速度大小为1单位长度每秒。当小球到达线段的端点（左端点或右端点）的时候，会立即向相反的方向移动，速度大小仍然为原来大小。当两个小球撞到一起的时候，两个小球会分别向与自己原来移动的方向相反的方向，以原来的速度大小继续移动。
现在，告诉你线段的长度L，小球数量n，以及n个小球的初始位置，请你计算t秒之后，各个小球的位置。

输入格式

输入的第一行包含三个整数n,L,t，用空格分隔，分别表示小球的个数、线段长度和你需要计算t秒之后小球的位置。

第二行包含n个整数a1,a2,…,an，用空格分隔，表示初始时刻n个小球的位置。

输出格式

输出一行包含n个整数，用空格分隔，第i个整数代表初始时刻位于ai的小球，在t秒之后的位置

样例输入1

3 10 5
4 6 8

1 2	3 10 5 4 6 8

样例输出1

7 9 9

7 9 9

样例解释

样例输入2

10 22 30
14 12 16 6 10 2 8 20 18 4

1 2	10 22 30 14 12 16 6 10 2 8 20 18 4

样例输出2

6 6 8 2 4 0 4 12 10 2

1	6 6 8 2 4 0 4 12 10 2

数据范围

对于所有评测用例，1 ≤ n ≤ 100，1 ≤ t ≤ 100，2 ≤ L ≤ 1000，0 < ai < L。L为偶数。保证所有小球的初始位置互不相同且均为偶数。

提示

因为所有小球的初始位置都为偶数，而且线段的长度为偶数，可以证明，不会有三个小球同时相撞，小球到达线段端点以及小球之间的碰撞时刻均为整数。

同时也可以证明两个小球发生碰撞的位置一定是整数（但不一定是偶数）。

题目分析

根据题目的描述我们可以知道，每次只会有两个小球碰撞在一起，且碰撞之后只改变运动方向，运动速度保持不变。那么，我们可以维护两个变量pos和dir，分别表示第i个小球在数轴上的位置和此时这个小球的运动方向。这样我们只需要判断小球是否碰触到了边界或其他小球（也就是同一时刻数轴上同一点有两个小球）即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;
int n, len, t;
struct ball
{
	int pos;
	bool dir;
} data[maxn]
inline int getint()
{
	int r = 0, k = 1;
	char c = getchar();
	for(; c < '0' || c > '9'; c = getchar())
		if(c == '-') k = -1;
	for(; c >= '0' && c <= '9'; c = getchar())
		r = r * 10 + c - '0';
	return r * k;
}
int main(int argc, char const *argv[])
{
	n = getint();
	len = getint();
	t = getint();
	for(int i = 1; i <= n; i++)
	{
		data[i].pos = getint();
		data[i].dir = false;
	}
	for(int now = 1; now <= t; now++)
	{
		for(int i = 1; i <= n; i++)
		{
			if(!data[i].dir)
			{
				data[i].pos++;
				// 碰到了右边界，反向      
				if(data[i].pos == len)
					data[i].dir = !data[i].dir;
			}
			else
			{
				data[i].pos--;
				//碰到了左边界，反向
				if(data[i].pos == 0)
					data[i].dir = !data[i].dir;
			}
		}
		for(int i = 1; i <= n - 1; i++)
		{
			for(int j = i + 1; j <= n; j++)
			{
				if(data[i].pos == data[j].pos)
				{
					// 两个小球相撞了，分别反向
					data[i].dir = !data[i].dir;
					data[j].dir = !data[j].dir;
				}
			}
		}
	}
	for(int i = 1; i <= n; i++)
		printf("%d ", data[i].pos);
	putchar('\n');
	return 0;
}