冒泡排序

Time Limit: 15 Sec  Memory Limit: 256 MB

Submit: 243  Solved: 108

[][][]

Description

　　下面是一段实现冒泡排序算法的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中元素的值会是什么样的呢？

Input

　　输入文件共2行。

　　第1行包含空格隔开的一个正整数n和一个非负整数k；

　　第2行包含n个空格隔开的互不相同的正整数，表示初始时a数组中的排列。

Output

　　输出文件共1行。

　　若在执行完整个代码之后执行swap的次数仍不够k，那么输出一个字符串”Impossible!”(不含引号)，否则按顺序输出执行swap操作k次之后数组a的每一个元素，用空格隔开。

Sample Input

1 1

1

Sample Output

Impossible!

HINT

 

n<=10^6

k<=10^12

题解：这道题目的话，首先要去分析冒泡排序，设g[x]表示一个数前面比其大的个数， 

那么交换z次后，其前面比它大的个数绝对减少min(g[x],z)，因为每一轮交换必定会交换下去一个比它大的数

所以可以二分出哪一轮。

然后二分出那一轮后

我们发现，g[i]<=x的话，那这个数一定排序完毕了。而对于g[i]>x的部分，他们相对于原数列的位置不变。

这样就可以求出做了x次外层循环后的结果了

 

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6  7 #define ll long long 8 #define N 1000007   9 using namespace std;10 inline ll read()11 {12     ll x=0,f=1;char ch=getchar();13     while(!isdigit(ch)){
    if(ch=='-')f=-1;ch=getchar();}14     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}15     return x*f;16 }17 18 int n;ll k;19 int a[N],mx[N],b[N],fz[N];20 bool boo[N];21 int tree[N];22 23 inline int lowbit(int x){
    return x&(-x);}24 int query(int x)25 {26     int res=0;27     for (int i=x;i>=1;i-=lowbit(i))28         res+=tree[i];29     return res;30 }31 void add(int x)32 {33     for (int i=x;i<=n+1;i+=lowbit(i))34         tree[i]+=1;35 }36 ll calc(int x)37 {38     ll res=0;39     for (int i=1;i<=n;i++)40         res+=min(mx[i],x);41     return res;42 }43 int main()44 {45     freopen("fzy.in","r",stdin);46     freopen("fzy.out","w",stdout);47     48     n=read(),k=read();49     for (int i=1;i<=n;i++)50         a[i]=read();51     for (int i=1;i<=n;i++)52     {53         mx[i]=query(n+1)-query(a[i]);54         add(a[i]);55     }56     int l=0,r=n;57     while(l
           
            >1;60 if (calc(mid)>=k) r=mid-1;61 else l=mid;62 }63 if (l==n)64 {65 puts("Impossible!");66 return 0;67 }68 k-=calc(l);int num=0;69 for (int i=1;i<=n;i++)70 if (mx[i]>r) b[i-r]=a[i];71 else fz[++num]=a[i];72 sort(fz+1,fz+num+1);73 num=0;74 for (int i=1;i<=n;i++)75 if (b[i]==0) b[i]=fz[++num];76 for (int i=1;i
            
             b[i+1])78 {79 swap(b[i],b[i+1]);80 k--;if (!k) break;81 }82 for (int i=1;i<=n;i++)83 printf("%d ",b[i]);84 }