VMSWAP - Đổi chỗ

Tác giả: flashmt

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
using namespace std;

int brute(int a[],int n)
{
	int best=0;
	for (int l=n-1;l;l--)
		for (int i=0;i+l<n;i++)
		{
			int j=i+l;
			if ((l-1)*2+1<=best) break;
			if (a[j]>a[i]) continue;
			int inc=0;
			for (int k=i+1;k<j;k++) 
			{
				if (a[k]>a[i]) inc--; else inc++;
				if (a[k]<a[j]) inc--; else inc++;
			}
			best=max(best,inc+1);
		}
	return best;
}

int main()
{
	int n,a[1000],inv=0;
	cin >> n;
	for (int i=0;i<n;i++) cin >> a[i];
	
	for (int i=0;i<n;i++) 
		for (int j=i+1;j<n;j++)
			inv+=a[i]>a[j];
	
	cout << inv-brute(a,n) << endl;
}

Download