题目描述
给定一个数列,求排序至少交换多少次可以使它有序
样例
输入:
5
9
1
0
5
4
3
1
2
3
0
输出:
6
0
(树状数组) $O(nlogn)$
(你品,你细品)
对于最小的一个数,设它在未排序数组中的下标为 $x$ ,则必须要交换 $(x-1)$ 次才能使得它到排序后的位置
如果交换次数最少,那么不应该有第二个数交换到最小的一个数前面,也就是说,我们可以不考虑最小的一个数了
所以说,我们可以忽略掉最小数,以第二小的数为最小数,第三小的数为第二小的数……以此类推
每次只需要求出需要目前的“最小数”交换多少次才能到第一位(因为“最小数”最终应该排在最前面)
(前方高能)
对于第 $i$ 次操作,设 $d$ 为不考虑前 $(i-1)$ 小的数时,从第一个数到“最小数”的距离,那么每次需要交换 $d$ 次才能到达排序后的位置
接下来有两个问题:
1. 如何求出“最小数”? 一种可行的方式是堆
2. 如何求出
不考虑前 $(i-1)$ 小的数时,从第一个数到“最小数”的距离”?
也就是说需要支持两个操作:
1. 每执行完一次操作,假如操作的数为 $x$ , 大于 $x$ 的所有数都不用考虑 $x$ 这个点了
2. 查询在 $x$ 前面还有多少个点需要考虑
1对应了单点修改,2对应了区间查询(而且是从1开始的)
那么就可以想到使用树状数组,而且还有常数小的优势
具体实现方法:
1. 所有数初始值设为 $1$
2. 查询操作只需要求 $1$ ~ $x$ 的和即可,基本操作
3. 操作完毕之后将操作数打上 $-1$ 标记,使得后面所有数求和都不会考虑这个点
注意 $500000*500000>1e9$ ,所以用 $long$ $long$ 存
时间复杂度
树状数组 $n$ 个点初始化每个 $O(logn) $
$n$ 次操作,每次从堆中取出元素 $O(logn)$
每次求和 $O(logn)$
每次打标记 $O(logn)$
总共还是 $O(nlogn)$
参考文献
神似谜一样的牛
C++ 代码
#include <cstdio>
#include <queue>
#include <utility>
#define lowbit(x) x&(-x)
using std::priority_queue ;
using std::pair ;
typedef long long ll ;
typedef pair<int,int> pii ;
const int N=500010 ;
ll tr[N] ;
int n ;
inline void add(int x,ll c)
{
for(ll i=x;i<=n;i+=lowbit(i)) tr[i]+=c ;
}
inline ll sum(int x)
{
ll res=0 ;
for(ll i=x;i;i-=lowbit(i)) res+=tr[i] ;
return res ;
}
int main()
{
while(~scanf("%d",&n),n)
{
priority_queue<pii> q ;
for(int i=1;i<=n;i++)
{
ll x ; scanf("%d",&x) ;
add(i,1),q.push({-x,i}) ;
//小技巧:priority_queue是大顶堆,所以变成负数就是小顶堆
}
ll ans=0 ;
for(int i=1;i<=n;i++)
{
int t=q.top().second ;
q.pop() ;
ans+=sum(t)-1 ;
add(t,-1) ;
}
printf("%lld\n",ans) ;
}
return 0 ;
}
纯净版代码(无STL,适合非C++的同学)
#include <cstdio>
#define lowbit(x) x&(-x)
typedef long long ll ;
const int N=500010 ;
ll tr[N] ;
int n ;
inline void swap(int &x,int &y) { if(x!=y) x^=y^=x^=y; }
struct type
{
int key[N],val[N] ;
int idx ;
void down(int u)
{
int t=u ;
if((u<<1)<=idx&&key[t]>key[u<<1]) t=u<<1 ;
if((u<<1|1)<=idx&&key[t]>key[u<<1|1]) t=u<<1|1 ;
swap(key[t],key[u]) ;
swap(val[t],val[u]) ;
if(t!=u) down(t) ;
}
void up(int u)
{
if((u>>1)>0&&key[u>>1]>key[u])
{
swap(key[u>>1],key[u]) ;
swap(val[u>>1],val[u]) ;
up(u>>1) ;
}
}
int top() { return val[1]; }
void pop() { key[1]=key[idx],val[1]=val[idx--],down(1); }
void push(int a,int b) { key[++idx]=a,val[idx]=b,up(idx); }
} q ;
inline void add(int x,int c)
{
for(int i=x;i<=n;i+=lowbit(i))
tr[i]+=c ;
}
inline ll sum(int x)
{
ll res=0 ;
for(int i=x;i;i-=lowbit(i)) res+=tr[i] ;
return res ;
}
int main()
{
while(~scanf("%d",&n),n)
{
for(int i=1;i<=n;i++)
{
ll x ; scanf("%d",&x) ;
add(i,1),q.push(x,i) ;
}
ll ans=0 ;
for(int i=1;i<=n;i++)
{
int t=q.top() ;
q.pop() ;
ans+=sum(t)-1 ;
add(t,-1) ;
}
printf("%lld\n",ans) ;
}
return 0 ;
}