脚本宝典收集整理的这篇文章主要介绍了【bzoj3580】冒泡排序，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
下面是一段实现冒泡排序算法的C++代码：
for (int i=1;i<n;i++) for (int j=1;j<=n-i;j++) if (a[j]>a[j+1]) swap(a[j],a[j+1]);
其中待排序的a数组是一个1~n的排列，swap函数将交换数组中对应位置的值。 对于给定的数组a以及给定的非负整数k，使用这段代码执行了正好k次swap操作之后数组a中元素的值会是什么样的呢？
输入文件共2行。 第1行包含空格隔开的一个正整数n和一个非负整数k； 第2行包含n个空格隔开的互不相同的正整数，表示初始时a数组中的排列。
输出文件共1行。 若在执行完整个代码之后执行swap的次数仍不够k，那么输出一个字符串”Impossible!”(不含引号)，否则按顺序输出执行swap操作k次之后数组a的每一个元素，用空格隔开。
1 1 1
Impossible!
n<=10^6 k<=10^12
【分析】
十分不错的一道题目，我们第$i$个数$a_i$，它前面有$p_i$个比他大的数，那么$k$轮内，它会被交换$min(p_i,k)$次
我们可以通过二分，确定交换了多少轮
假设交换了$t$轮，那么所有满足$p_i ge t$的就仅向前移动了t个位置
剩下的数字直接按大小排序填上就好了，因为次数够他们排到自己的位置了
然后把剩下的一些操作次数给模拟走一下即可
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+5; int c[maxn],n,a[maxn]; ll gs; int res[maxn]; int lowbit(int x) { return x&(-x); } void add(int x,int val) { while(x<=n) { c[x]+=val; x+=lowbit(x); } } int getsum(int x) { int res=0; while(x) { res+=c[x]; x-=lowbit(x); } return res; } int pos,b[maxn],p[maxn]; ll cnt; void work(int mid) { cnt=0; for(int i=1;i<=n;i++) cnt+=1ll*min(p[i],mid); } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d%lld",&n,&gs); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { p[i]=getsum(n)-getsum(a[i]); add(a[i],1); } int l=1,r=n,ans=0; while(l<r) { int mid=l+r>>1; work(mid); if(cnt<gs) ans=mid,l=mid+1; else r=mid-1; } work(ans+1); if(cnt<gs) ans++; work(ans+1); if(gs>cnt) { printf("Impossible!"); return 0; } work(ans); for(int i=1;i<=n;i++) { if(p[i]>ans) res[i-ans]=a[i]; else b[++pos]=a[i]; } sort(b+1,b+pos+1); pos=0; for(int i=1;i<=n;i++) if(!res[i]) res[i]=b[++pos]; for(int i=1;i<n && cnt<gs;i++) { if(res[i]>res[i+1]) { swap(res[i],res[i+1]); cnt++; } } for(int i=1;i<=n;i++) printf("%d ",res[i]); return 0; }
以上是脚本宝典为你收集整理的【bzoj3580】冒泡排序全部内容，希望文章能够帮你解决【bzoj3580】冒泡排序所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。