随笔 - 32  文章 - 2  trackbacks - 0
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 8799
  • 排名 - 1247

最新评论

阅读排行榜

评论排行榜

用了树状数组,尽管还不太理解。归并排序统计逆序对个数也可以。
 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)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理