用了树状数组，尽管还不太理解。归并排序统计逆序对个数也可以。
1 #include <iostream>
2 using namespace std;
3 const int OO=10000000;
4 int n,k;
5 int list[10011];
6 int sum;
7 int mm,ans=1;
8 int num[10011];
9 int t[10011];
10
11 int lowbit(int x){
12 return x&(-x);
13 }
14
15 void newrow(){
16 for (int i=1;i<=10011;++i) t[i]=0;
17 }
18
19 int SUM(int x){
20 int re=0;
21 while (x>0){
22 re+=t[x];
23 x-=lowbit(x);
24 }
25 return re;
26 }
27
28 int insert(int x){
29 while (x<=n){
30 ++t[x];
31 x+=lowbit(x);
32 }
33 }
34
35 int main(){
36 scanf("%d %d",&n,&k);
37 for (int i=1;i<=k;++i){
38 newrow();
39 sum=0;
40 for (int j=1;j<=n;++j) scanf("%d",&list[j]);
41 for (int j=1;j<=n;++j){
42 sum+=j-SUM(list[j]);
43 insert(list[j]);
44 }
45 if (sum>mm){
46 mm=sum;
47 ans=i;
48 }
49 }
50 cout<<ans;
51 }
52
posted on 2008-11-10 20:12
Joseph 阅读(925)
评论(0) 编辑 收藏 引用