zercal
C++博客
首页
新随笔
联系
聚合
管理
10 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔档案
2007年10月 (10)
搜索
最新评论
阅读排行榜
1. PKU1639最小度限制生成树(1055)
2. PKU推荐题目(562)
3. 单元最短路(dijkstra+堆)不是很精简(385)
4. 匈牙利算法求二分图最大匹配(371)
5. 拓扑排序求逆序对(348)
评论排行榜
1. PKU推荐题目(0)
2. 南京挂了(0)
3. PKU1639最小度限制生成树(0)
4. 调整状态...努力...(0)
5. 单元最短路(dijkstra+堆)不是很精简(0)
拓扑排序求逆序对
#include
<
iostream
>
using
namespace
std;
int
a[
110000
],b[
110000
],res;
//
res需要赋初值0
int
merge(
int
st,
int
mid,
int
ed)
{
int
sa,ea,sb,eb,i,j;
sa
=
st,ea
=
mid,sb
=
mid
+
1
,eb
=
ed;i
=
j
=
0
;
while
(sa
<=
ea
&&
sb
<=
eb)
{
if
(a[sa]
<=
b[sb])
b[i
++
]
=
a[sa
++
];
else
{
b[i
++
]
=
a[sb
++
];
res
+=
mid
+
1
-
sa;
}
}
while
(sa
<=
ea)
b[i
++
]
=
a[sa
++
];
while
(sb
<=
eb)
b[i
++
]
=
b[sb
++
];
for
(j
=
0
;j
<
i;j
++
)
a[st
+
j]
=
b[j];
return
0
;
}
int
mst(
int
st,
int
ed)
{
int
mid,i,j,k;
if
(st
<
ed)
{
mid
=
(st
+
ed)
/
2
;
mst(st,mid);
mst(mid
+
1
,ed);
merge(st,mid,ed);
}
return
0
;
}
posted on 2007-10-06 19:48
zercal
阅读(348)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © zercal