MergeAndCount_Fighting strength vs Equipment

1.Discription：

If you play games, you will know the importance of your equipment. However, your equipment is not the only thing to determine your success. Therefore, there are a lot of people winning without precious equipment because of their high fighting strength. Now, you are given a fighting strength of each people, (a1, a2, a3,..., an). And the list is sorted according to their equipment value from low to high. Your target is to find how many such pairs (i, j) exists where ai is bigger than aj which means people i with lower equipment but higher fighting strength than people j.

Input

The first line is just an integer n (n is a positive and less than 1000000).

The second line are n integers a1, a2, a3,...,an( abs (ai) is less than 2^31)

Output

You just need to output the number of pairs described above .

Sample Input

5
3 2 1 4 5

Sample Output

3

2.coding

? 实质就是 merge and count。lc 上的 k个逆序对，就是这道题目。

#include<iostream>
using namespace std;
long long int sum = 0;
void merge(long long int arr[], int start, int mid, int end) {
	//复制左右两边的
	long long int *left = new long long int[mid - start + 1];
	for (int i = 0, j = start; i < mid - start + 1; ++i)
		left[i] = arr[j++];

	long long int *right = new long long int[end - mid];
	for (int i = 0, j = mid + 1; i < end - mid; ++i)
		right[i] = arr[j++];

	//合并到 arr 之中去
	int left_index = 0, right_index = 0;
	for (int i = start; i <= end; ++i) {
		if (left_index <= mid - start &&
			(right_index >= end - mid || left[left_index] <= right[right_index]))
			arr[i] = left[left_index++];
		else {
			arr[i] = right[right_index++];
			if (left_index <= mid - start) {
				sum += (mid - start - left_index + 1);
			}
		}//右边的更小，就添加进来
	}
}
void divide(long long int arr[], int start, int end) {
	if (start >= end)
		return;
	else {
		int mid = (start + end) / 2;
		divide(arr, start, mid);
		divide(arr, mid + 1, end);
		//把 start~end 的合起来
		merge(arr, start, mid, end);
	}
}

int main() {
	int n;
	cin >> n;
	long long int *arr = new long long int[n];
	for (int i = 0; i < n; ++i)
		cin >> arr[i];
	divide(arr, 0, n - 1);
	cout << sum << endl;
	system("pause");
	return 0;
}

MergeAndCount

原文：https://www.cnblogs.com/nujer/p/14517670.html