《挑战程序设计竞赛》3.2.3 常用技巧-弹性碰撞 POJ3684 2674

本文主要是介绍《挑战程序设计竞赛》3.2.3 常用技巧-弹性碰撞 POJ3684 2674，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

POJ3684

http://poj.org/problem?id=3684

题意

将N个半径为R的球放入一个圆桶（圆桶口径刚好放入一个球），将圆桶竖直放着，最下端距离地面H高度，让球每隔一秒自由下落，求T时刻各个球距离地面的高度。

思路

将球最开始的位置均视为H，即忽略球本身的高度，这样球碰撞就可视为互相穿过继续运动。然后就可以分别单独求出每个球T时刻的高度后排序就是答案了。排序后再加上每个球原本高于高度h的值。
需要注意的地方：
（1）t可能小于n，需要特殊处理，不知道测试数据是否有涉及到。
（2）r给的值单位是cm，要换算成m。

代码

Source CodeProblem: 3684       User: liangrx06
Memory: 248K        Time: 0MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;int main(void)
{int c, n, t;double h, r, g = 10;double pos[100];cin >> c;while (c--) {cin >> n >> h >> r >> t;fill(pos, pos+n, h);double T = sqrt(2*h/g);for (int i = 0; i < n && i < t; i ++) {int t0 = (t-i)/T;double t1 = t-i - t0*T;if (t0 % 2 == 0)pos[i] -= (g*t1*t1/2);elsepos[i] -= (g*(T-t1)*(T-t1)/2);}sort(pos, pos+n);for (int i = 0; i < n; i ++)printf("%.2lf%c", pos[i]+2*i*r/100, (i==n-1) ? '\n' : ' ');}return 0;
}

POJ2674

http://poj.org/problem?id=2674

题意

题目大意是，在一个一维的世界里有N个居民在一条直线上的不同位置，他们以恒定的速度大小，速度方向可能不同进行运动，相遇后会返回，问给定线段的长度l，速度v，求最后一个走出这个范围的居民是谁，用时多少。

思路

这类弹性碰撞可视为直接穿过。举个例子，我们可以想象一下几个质量相同刚体（忽略他们的半径）在同一直线上运动，速度方向可能不同，所以会发生弹性碰撞，假设没有任何能量损耗的话，碰撞后是彼此交换速度后返回的，如果求在t时刻，这些球的位置该如何求。因为相遇后彼此交换了速度后返回，所以实际上相当于碰撞后各个球还是继续沿着原来的方向运动，所以可以求出t时刻这些刚体的分散在的位置，但是不能对上号，因为实际上发生碰撞后会返回的，但是注意一个细节就是不管这些球如何碰撞多少次，它们之间的相对顺序是不会变化的，所以对求出来的位置进行排个序就可以对上号了。
因此这个题的复杂度是O(N)。
另外这个题有两个恶心的地方：
（1）一个方向标记，还搞大小写两种，题目里好像根本没说明啊，害的我WA了好几次，看了别人的代码才知道。
（2）结果小数点2位之后的数是直接截断的，并不是四舍五入，因此不可以直接打印，要先处理再打印。

代码

Source CodeProblem: 2674       User: liangrx06
Memory: 8108K       Time: 579MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
using namespace std;const int N = 32000;int main(void)
{int n;double l, v;while (cin >> n && n) {cin >> l >> v;int pnum = 0;double pmaxt = -1, nmaxt = -1;char dir[2];double pos;char name[N][251];for (int i = 0; i < n; i ++) {scanf("%s%lf%s", dir, &pos, name[i]);if (dir[0] == 'p' || dir[0] == 'P') {pnum ++;if (pmaxt < 0)pmaxt = (l-pos)/v;}else {nmaxt = pos/v;}}if (pmaxt > nmaxt)printf("%13.2lf %s\n", (int)(pmaxt*100)/100.0, name[n-pnum]);elseprintf("%13.2lf %s\n", (int)(nmaxt*100)/100.0, name[n-pnum-1]);}return 0;
}