POJ 2674-Linear world（弹性碰撞）

Time Limit: 3000MS
Memory Limit: 65536K

Total Submissions: 3119
Accepted: 696

Description

The Disc, being flat, has no real horizon. Any adventurous sailors who get funny ideas from staring at eggs and oranges for too long and set out for the antipodes soon learned that the reason why distant ships sometimes looked as though they were disappearing over the edge of the world was that they were disappearing over the edge of the world. (Terry Pratchett -Colour of Magic)

Not so long time ago people used to believe that they live on 2-D world and if they will travel long enough in one direction, they will fall down over the edge. Even when it was proved that the Earth is rounded some of them were still afraid to travel to the southern hemisphere.

Try to imagine one 1-D (linear) world. On such world there are only two possible directions (left and right). All inhabitants of such world were created exactly at the same time and suddenly all of them start to move (all with same constant velocity) in one or the other direction. If two inhabitants encounter each other, they politely exchange greetings and then they turn around and start to move in an opposite direction. When an inhabitant reaches the end of the world he falls away and disappears.

Your task is to determine, for a given scenario of creation, which inhabitant and when (counting from the moment of creation) will be the last one to fall away. You can assume that the time required to exchange greetings and turn around is 0.

Input

The input consists of multiple descriptions (data sets) of the creation moment. File structure is as follows:

DIR POS NAME

...

The first line defines the number of inhabitants (N<32000). Data set starting with value N=0 represents the end of the input file. The second line contains length of the world L(float) and velocity of inhabitants V(float). Both values are always positive. In next N lines the data about inhabitants are given in an order of increasing POS (positive direction):

DIR – initial direction ('p' or 'P' for positive and 'n' or 'N' for negative)

POS – position in the time of creation (0<=POS<=L)

NAME – name of inhabitant (string up to 250 characters)

Input values within one line are separated with at least one space and there will be no empty lines in input. You may assume that input is always correct and that each data set has only one unique solution.

Output

The output consists of one line per each input data set. The first value should be the time when the last inhabitant will fall of the linear world counting from the moment of creation. Value should be printed truncated to two decimal places in a field 13 characters wide. The second value should be the name of the inhabitant. Values should be separated with single space character.

Sample Input

13.5 2

p 3.5 Smarty

4 10 1

n 3 Joanna

p 1 Helga

n 7 Clever

p 5 Venus

Sample Output

         5.00 Smarty
         9.00 Venus

题意：在一个线性世界，有n个居民，每个人都在自己的初始位置pos上，运动方向分别为P（正方向）和N（负方向）。 线性世界长度为L，所有居民移动速度都为v。居民们相遇时，就会自动掉头。从初始时刻开始运动，问最后一个掉下去的运动了多长时间，且输出姓名。
思路：
典型的弹性碰撞模型（详见《挑战程序设计竞赛》）。这个技巧的主要思想是：弹性碰撞模拟起来又困难又慢，所以我们这样假设：两个球在碰撞之后并不返回，而是继续向前，只不过交换了一下标号
对于这个题目，最后一个落出世界的人所花费的时间很好统计，只要找到距离边界最远的点X即可。
还有一个问题，如何知道最后一个落出世界的人是谁？
这个要看运动时间最长的居民和哪些居民交换了姓名，最后一个交换的就是最后一个掉下去的。
这时我们再这样考虑，除了X点外，其他点相撞时不交换标号，只是擦肩而过，这样，X点只能与他前进方向上反向的球相撞，而且相撞的次数n是固定的。
继续往下思考，由于是弹性碰撞，无论前进方向是怎样的，一定是按照与边界距离的远近依次掉落的，不管它的方向是啥。所以最后掉落的n个球一定是X球后的n个球！！！
所以一定与这n个球交换了标号
代码：

  1 /*
  2 * @FileName: D:代码与算法2017训练比赛七月训练四1012.cpp
  3 * @Author: Pic
  4 * @Date:   2017-08-04 15:53:57
  5 * @Last Modified time: 2017-08-04 16:25:53
  6 */
  7 
  8 #include <iostream>
  9 #include <algorithm>
 10 #include <cstdio>
 11 #include <string.h>
 12 #include <queue>
 13 using namespace std;
 14 typedef long long LL;
 15 const int MAXN=1e3+30;
 16 const LL INF=0x80808080;
 17 LL a[MAXN];
 18 struct node
 19 {
 20 	int x,y;
 21 };
 22 LL hs[MAXN*MAXN];
 23 node co[MAXN*MAXN];
 24 int n;
 25 int cnt=0;
 26 bool seach(LL x)
 27 {
 28 	for(int i=0;i<n;i++){
 29 		if(a[i]==x) continue;
 30 		LL flag=x-a[i];
 31 		int id=lower_bound(hs,hs+cnt,flag)-hs;
 32 		while(hs[id]==flag){
 33 			if(((LL)min(co[id].x,co[id].y))!=min(a[i],x)&&((LL)max(co[id].x,co[id].y))!=max(a[i],x)){
 34 				return 1;
 35 			}
 36 			id++;
 37 		}
 38 	}
 39 	return 0;
 40 }
 41 int main(){
 42 	//freopen("data.in","r",stdin);
 43 	while(~scanf("%d",&n)&&n){
 44 		for(int i=0;i<n;i++){
 45 			scanf("%lld",&a[i]);
 46 		}
 47 		sort(a,a+n);
 48 		cnt=0;
 49 		for(int i=0;i<n;i++){
 50 			for(int j=i+1;j<n;j++){
 51 				co[cnt].x=a[i],co[cnt].y=a[j];
 52 				hs[cnt++]=a[i]+a[j];
 53 			}
 54 		}
 55 		sort(hs,hs+cnt);
 56 		LL res=-1*INF;
 57 		for(int i=n-1;i>=0;i--){
 58 			if(seach(a[i])){
 59 				res=a[i];
 60 				break;
 61 			}
 62 		}
 63 		if(res!=(-1*INF)){
 64 			printf("%lld
",res);
 65 		}
 66 		else{
 67 			printf("no solution
");
 68 		}
 69 	}
 70     return 0;
 71 }

View Code