【HDU】5775 Bubble Sort

本文主要是介绍【HDU】5775 Bubble Sort，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Bubble Sort

---

题目链接

• Bubble Sort

---

题目大意

    一个1～n的序列冒泡排序，求每个元素在排序中达到的最右位置和最左位置的差值。

---

题解

逆序对

    注意到每个元素只有右边有元素比他小的时候才会向右移动，所以最右端的位置一定是i+k，i为当前位置，k为该元素右边的逆序对数；又因为每个元素最后的位置一定在$a_i$，所以，最左端的位置一定是$\min (a_i,i)$，相减即可。

    逆序对的话线段树树状数组什么的都可以。

---

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 100005using namespace std;struct tree
{int l,r,val;
};
tree d[maxn<<2];
int T,a[maxn],ans[maxn],n;void buildtree(int n,int l,int r)
{d[n].l=l; d[n].r=r; d[n].val=0;if (l==r) return ;int mid=(l+r)>>1;buildtree(n<<1,l,mid);buildtree(n<<1|1,mid+1,r);
}int Count(int n,int l,int r)
{if (l>r) return 0;if (d[n].l==l && r==d[n].r) return d[n].val;int mid=(d[n].l+d[n].r)>>1;if (r<=mid) return Count(n<<1,l,r);else if (l>mid) return Count(n<<1|1,l,r);else return Count(n<<1,l,mid)+Count(n<<1|1,mid+1,r);
}void Insert(int n,int p)
{if (d[n].l==d[n].r){d[n].val=1;return ;}int mid=(d[n].l+d[n].r)>>1;if (p<=mid) Insert(n<<1,p);else Insert(n<<1|1,p);d[n].val++;
}int main()
{int Case=1;scanf("%d",&T);while (T--){memset(a,0,sizeof(a));memset(d,0,sizeof(d));memset(ans,0,sizeof(ans));scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);buildtree(1,1,n);for (int i=n;i>=1;i--){int k=Count(1,1,a[i]-1);Insert(1,a[i]);ans[a[i]]=i+k-min(a[i],i);}printf("Case #%d: ",Case++);for (int i=1;i<n;i++) printf("%d ",ans[i]);printf("%d\n",ans[n]);}return 0;
}

这篇关于【HDU】5775 Bubble Sort的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---