bzoj 3580 冒泡排序乱搞+思维

冒泡排序

Time Limit: 15 Sec Memory Limit: 256 MB
Submit: 243 Solved: 108
[Submit][Status][Discuss]

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<cstring>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<cmath>
 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<r)
58     {
59         int mid=(l+r+1)>>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<n;i++)
77         if (b[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 }