Note: This article is available in Chinese only. 本文暂无英文版本。
View original
#
题意：
这题是问一个长度为n的循环数组中，逆序对最少的个数。。。
我们可以先用树状数组求出初始的数列的逆序对。。。
然后其他的可以通过递推得到。。。。
当a[i]从处于位置1而被放到最后的时候。。。
cnt = cnt -a[i]+n-a[i]+1;
然后取所有cnt的最大值就行。
代码实现
1/*************************************************************************
2 > File Name: code/hud/1394.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年10月28日 星期三 21时16分47秒
6 ************************************************************************/
7#include<iostream>
8#include<iomanip>
9#include<cstdio>
10#include<algorithm>
11#include<cmath>
12#include<cstring>
13#include<string>
14#include<map>
15#include<set>
16#include<queue>
17#include<vector>
18#include<stack>
19#include<cctype>
20#define yn hez111qqz
21#define j1 cute111qqz
22#define ms(a,x) memset(a,x,sizeof(a))
23using namespace std;
24const int dx4[4]={1,0,0,-1};
25const int dy4[4]={0,-1,1,0};
26typedef long long LL;
27typedef double DB;
28const int inf = 0x3f3f3f3f;
29const int N=5E3+7;
30int c[N];
31int n,a[N];
32int lowbit( int x)
33{
34 return x&(-x);
35}
36void update ( int x,int delta)
37{
38 for ( int i = x ; i <= n ; i = i + lowbit(i)) c[i] = c[i] + delta;
39}
40int Sum( int x)
41{
42 int res = 0 ;
43 for ( int i = x ;i >= 1; i = i - lowbit(i))
44 {
45 res = res + c[i];
46 }
47 return res;
48}
49int main()
50{
51#ifndef ONLINE_JUDGE
52 freopen("in.txt","r",stdin);
53#endif
54 while (scanf("%d",&n)!=EOF)
55 {
56 ms(c,0);
57 for ( int i = 1 ; i <= n ; i++)
58 {
59 scanf("%d",&a[i]);
60 a[i]++;
61 }
62 int cnt = 0 ;
63 int ans = inf;
64 for ( int i = 1 ; i <= n ; i++)
65 {
66 update(a[i],1);
67 cnt = cnt + i - Sum(a[i]);
68 }
69 if (cnt<ans) ans = cnt;
70 for ( int i = 1 ; i <= n ; i++)
71 {
72 cnt =cnt -a[i]+n-a[i]+1;
73 if (cnt<ans&&cnt>0) ans = cnt;
74 }
75 printf("%d\n",ans);
76 }
77#ifndef ONLINE_JUDGE
78 fclose(stdin);
79#endif
80 return 0;
81}