hnu 12264 collisions

题目：

Collisions

Time Limit: 10000ms, Special Time Limit:25000ms, Memory Limit:65536KB

Total submit users: 10, Accepted users: 7

Problem 12264 : No special judgement

Problem description

Identical small balls are located on a straight line and can move along this line only. Each ball moves with a constant velocity, but velocities of different balls may be different. When two balls meet, a perfectly elastic collision occurs. It’s a common-known physical fact, that when two equal-mass physical bodies A and B collide perfectly elastically, they swap their velocities, i.?e. new A’s velocity is old B’s one, and new B’s is old A’s.
Your task is to write a program to find the total number of collisions.

Input

The first line at input contains the number of balls N (3 ≤ N ≤ 2000000). Each of the following N lines contains 2 space-separated integers — the starting coordinate and the velocity of corresponding ball. All start coordinates are in range -10¹¹ < x_i < 10¹¹, all velocities are in range -10⁸ < v_i < 10⁸. All start coordinates are different. It’s guaranteed that each collision involves exactly two balls (none involves three or more balls together).

Output

Your program should output exactly one integer number in a single line ? the total number of collisions (or 987654321987654321 if the number is infinite).

Sample Input

Sample Output

Problem Source

2010 All-Ukrainian Collegiate Programming Contest Vinnytsia National Technical University

题意：就是告诉你有n，个小球，第二行是n个小球的位置和速度，所有小球都在一条直线上，小球相碰后交换速度，问最多有几次碰撞。如果无数次，输出987654321987654321.

思路：开始毫无思路，后来想了一下，相碰后交换速度，不是等价于直接穿过去吗，如果把小球按位置排序，即从小到大排序，然后求速度的逆序数不就行了吗？比如两个小球，一前一后分别为5,4，者后面小球会追上相碰，或者4，-3，也一样，还有，-1，-2，也是那个道理，所以题目就是叫你求逆序数。那样就不会有无数次的情况了，真的吗？答案是对的。求逆序数有两种方法，归并排序和树状数组，至少我知道这两种，不太会用，归并用了个模板，一次就过了，还是挺惊讶的。

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int size=2000500;
 5 __int64 date[size];
 6 struct point{
 7 __int64 position,v;
 8 };
 9 point temp[size];
10 int n;
11 __int64 L[size];
12 __int64 R[size];
13 const int Max = 1 <<30;
14 __int64 change = 0;
15 bool cmp(point x,point y)
16 {
17 return x.position<y.position;
18 }
19 
20 void Merge(__int64 *data,int left,int divide,int right)
21 {
22     int lengthL = divide - left;
23     int lengthR = right - divide;
24     
25     for(int i = 0; i < lengthL; ++i)
26     {
27         L[i] = data[left + i];
28     }
29     for(int i = 0; i < lengthR; ++i)
30     {
31         R[i] = data[divide + i];
32     }
33     L[lengthL] = R[lengthR] = Max;
34     int i = 0;
35     int j = 0;
36     for(int k = left; k < right; ++k)
37     {
38         if(L[i] <= R[j])
39         {
40             data[k] = L[i];
41             ++i;
42         }
43         else 
44         {
45             change += divide - i - left ;
46             data[k] = R[j];
47             ++j;
48         }
49     }
50 
51 }
52 
53 void MergeSort(__int64 *data,int left,int right)//归并排序求逆序数
54 {
55     if(left < right -1)
56     {
57         int divide = (left + right)/2;
58         MergeSort(data,left,divide);
59         MergeSort(data,divide,right);
60         Merge(data,left,divide,right);
61     }
62 }
63 
64 
65 
66 int main()
67 {
68 scanf("%d",&n);
69 for(int i=0;i<n;i++)
70 scanf("%I64d%I64d",&temp[i].position,&temp[i].v);
71 sort(temp,temp+n,cmp);//按位置排序
72 for(int i=0;i<n;i++)
73 date[i]=temp[i].v;
74 MergeSort(date,0,n);
75 cout<<change<<endl;
76 //system("pause");
77 return 0;
78 }

***************************************************************************************

总结：

1.基本代码要会敲，比如归并

2.相信自己，比如不会有无数次的情况

3.多练