Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #224 - bài NKINV theo hướng chia để trị
Ngày: 07-11-2012
Cập nhật: 07-11-2012
Người gửi: quandum
Ngôn ngữ: C++
Xem: 383

Điểm: 4.0/5 (7 Phiếu)


/*
coder: quandum - VNOI
Problem: http://vn.spoj.pl/problems/NKINV/
cinv(a) la so day nghich the cua day a[0..n-1], n phan tu.
Dat L=a[0..(n/2)-1] va R=a[n/2..n-1]
cinv(a)=cinv(L)+cinv(R)+z
voi z la so cap nghich the nam o 2 ben moc n/2
*/
#include <cstdio>
#include <vector>
#define maxn 60003
#define maxa 60004
using namespace std;
int n;	vector <int>a;
int cinv(vector <int> &a){
	int n=a.size();
	if (n<=1)
		return 0;
	vector <int> L,R;	L.clear();	R.clear();
	int x,y,z,j,i,mid=n/2;
	for (i=0;i<mid;i++)
		L.push_back(a[i]);
	for (i=mid;i<n;i++)
		R.push_back(a[i]);
	x=cinv(L);		y=cinv(R);		z=0;		i=0;		j=0;
	int nL=L.size(),nR=R.size();		L.push_back(maxa);	R.push_back(maxa);
	for (i=0;i<nL;i++){
		for (j=j;L[i]>R[j];j++)
			a[i+j]=R[j];
		a[i+j]=L[i];
		z+=j;
	}
	for (j=j;j<nR;j++)
			a[i+j]=R[j];
	return x+y+z;
}
void readin(){
	scanf("%d",&n);
	int x,i;		a.clear();
	for (i=0;i<n;i++){scanf("%d",&x);	a.push_back(x);}
}
int main(){
	readin();
	printf("%d",cinv(a));
	return 0;
}