Java教程

【bzoj3580】冒泡排序

本文主要是介绍【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】冒泡排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!