【bzoj3580】冒泡排序
2021/11/19 6:11:35
本文主要是介绍【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】冒泡排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求