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

08/11/2016 5 minutes read
Share:

Đề 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)

Các 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:

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

  • Tôi sẽ sắp xếp dãy đã cho theo thứ tự giảm dần. Và trong quá trình trộn tôi 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:

(Các 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 tôi 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 tôi 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 các 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;
}
view raw INVCNT.cpp hosted with ❤ by GitHub

Code by Phạm Văn Lâm.

Share: