小金自從進了集訓隊，做了很多有關于逆序對的題目，他也很喜歡逆序對。介紹一下逆序對。逆序對就是在一個陣列序列中的兩個數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 <stdio.h>
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/66009.html
標籤：基礎類
下一篇：．關鍵路徑 【問題描述】 已知一個AOE-網（邊表示活動的網，有向網路），求源點到匯點的關鍵路徑。 【基本要求】 ⑴建立AOE-網的存盤結構； ⑵求出所有的關鍵