小金自从进了集训队,做了很多有关于逆序对的题目,他也很喜欢逆序对。介绍一下逆序对。逆序对就是在一个数组序列中的两个数x和y,但这两个数x和y可以算作一个逆序对的规则是x要大于y,但x的位置一定要在y的前面(即i < j && a[i] > a[j] )。
那么小金的问题来了,如果给定一个长度为n的序列,这n个数保证大于等于0且小于n,并且不会重复。那么小金给了你一个移动操作,你可以将这个序列的第一个数拿到序列的最后将序列变为一个新的序列,例如当n=10的时候,给定一个序列。
那么,所有可能通过移动得到的序列如下。
请你输出在所有可能出现的序列中逆序对的个数最小的是多少?
Input
多组输入。
第一行输入整数n,含义如题意描述。(0 < n < = 5000)
第二行有n个整数(0 < = x < = n-1)。
Output
输出最小逆序对的个数。输入输出各占一行,保证数据合法。
Example Input
10
1 3 6 9 0 8 5 7 4 2
Example Output
16
#include
int main()
{
int i, n, a[5005], s[5005] = {0}, min;
while (~scanf("%d", &n))
{
int t, j, l;
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
for (l = j; l < n; l++)
{
if(a[j] > a[l])
s[i]++;
}
}
t = a[0];
for (j = 0; j < n; j++)
{
a[j] = a[j+1];
}
a[j-1] = t;
}
min = s[0];
for (i = 1; i < n; i++)
{
if(s[i] < min)
min = s[i];
}
printf("%d\n", min);
}
return 0;
}