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;
}