SPOJ.COM - Thuật toán bài INVCNT - Inversion Count

Posted on November 8th, 2016

Đề bài:

Cho một mảng gồm N phần tử là số nguyên dương, phân biệt A[0....N-1]. Nếu i < j và A[i] > A[j] thì cặp (i, j) gọi là một cặp đảo nghịch. Cho số N và mảng A. Nhiệm vụ của bạn là tìm ra số cặp đảo nghịch.

Đầu vào

Dòng đầu tiên là số nguyên t - số lượng test case, theo sau là một khoảng trống. Mỗi test case bắt đầu bằng số N, N <= 200000. Sau đó là N + 1 dòng, với dòng thứ i là phần tử A[i - 1], A[i - 1] <= 10^7. Dòng thứ N + 1 là dòng trống.

Đầu ra

Mỗi test case in ra trên 1 dòng là số cặp đảo nghịch.

Ví dụ

Đầu vào:

2

3
3
1
2

5
2
3
8
6
1

Đầu ra:

2
5

Giải thích:

  • Test case 1: có 2 cặp đảo nghịch là (3, 1) và (3, 2)
  • Test case 2: có 5 cặp đảo nghịch là (2, 1), (3, 1), (8, 6), (8, 1) và (6, 1)

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/INVCNT/

Phân tích

  • Mình sẽ sử dụng thuật toán tham lam Greedy để giải bài toán. Cụ thể hơn là mình sẽ sử dụng thuật toán sắp xếp trộn Merge Sort để giải quyết.

  • Mình sẽ sắp xếp dãy đã cho theo thứ tự giảm dần. Và trong quá trình trộn mình sẽ cập nhật kết quả. Nghe tới đây có vẻ khó hiểu, xin mời bạn theo dõi code dưới đây để hiểu rõ hơn.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include<iostream>
using namespace std;

const int MAX = 200005;

long long Answer;
int N, T;
int A[MAX];

void Merge(int *a, int left, int m, int right)
{
	int *temp = new int[right - left + 1];
	int k = 0, i = left, j = m + 1;

	while(i <= m && j <= right)
	{
		if(a[i] > a[j])
		{
			temp[k++] = a[i++];
			
			// Rõ ràng ở đây i < j mà a[i] > a[j]
			// thì ta đã có cặp đảo nghịch ở đây.
			// Hơn nữa, bạn để ý rằng, vì tôi sắp xếp dãy giảm dần
			// nên nếu a[i] > a[j] thì a[i] cũng sẽ lớn hơn các số ở nhánh phải
			// chú ý là tôi đang trộn 2 nhánh đã sắp xếp, nên a[j] là số lớn nhất
			// nghĩa là tôi có thêm (right - j + 1) cặp đảo nghịch
			Answer += right - j + 1;
		}
		else 
		{
			temp[k++] = a[j++];
		}
	}

	while(i <= m) temp[k++] = a[i++];
	while(j <= right) temp[k++] = a[j++];

	for(int i = 0; i < k; i++)
		a[i + left] = temp[i];
	delete[] temp;
}

void MergeSort(int *a, int left, int right)
{
	int m;
	if(left < right)
	{
		m = (left + right) / 2;
		MergeSort(a, left, m);
		MergeSort(a, m + 1, right);
		Merge(a, left, m, right);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);

	cin >> T;
	for(int tc = 0; tc < T; tc++)
	{
		//input
		Answer = 0;
		cin >> N;
		for(int i = 0; i < N; i++)
			cin >> A[i];

		// implementing code below
		MergeSort(A, 0, N-1);

		//output
		cout << Answer << endl;
	}
	return 0;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!