#C241119B. 冒泡排序

标签（Label）

逆序对
思维
二分答案
树状数组

网址（Website）

题目详情 - 冒泡排序 - Super

题解 - 冒泡排序 - Super

题目（Problem）

程序源代码

>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]);

样例

输入数据 1

1 1
1

输出数据 1

Impossible!

输入数据 2

5 5
5 4 3 2 1

输出数据 2

3 4 2 1 5

【样例 3】
见附加文件中的 sort/ex_sort3.in与sort/ex_sort3.ans。

题解（Solution）

30分

直接暴力查询修改，时间复杂度 $O(n^2)$ 。

100分

看到这个题的时候后有一种感觉，就是要快速求出大的循环运行 $i$ 次后的 $a_i$ 的样子，此时 $\verb!swap!$ 小于 $k$ ，并且保证跑第 $i+1$ 次时总的 $\verb!swap!$ 次数大于 $k$ ，然后暴力去把剩下的操作 $O(n)$ 解决，这样总时间复杂度还是 $O(n)$ 的，可以通过这道题。

如何求出第 $i$ 次运行呢？我们容易想到求逆序对，令 $f_i$ 表示前面大于 $a_i$ 的数，那么每次移动就会使 $f_i$ 减少 $1$ ，如果 $f_i=0$ ，那么就不会再减。每次更新 $f_i$ 时间是 $O(n)$ 的，发现每操作一层（即大循环运行 $1$ 次），总的 $\verb!swap!$ 次数就是 $\sum_{i=1}^N \min(f_i, x)$ ，其中 $x$ 为当前操作层数。我们很容易想到直接二分答案，每次计算层数。

求出层数之后，对于 $f_i \ge x$ （$x$ 意义与之前相同），由于这个数前面还有比它大的数，因此它不会主动向后移动，只会向前移动 $x$ 次；对于 $f_i < x$ ，由于当前数前面没有比它大的数，那么所有的满足 $f_i < x$ 的数会构成一个单增序列，直接填空即可。

最后暴力 $O(n)$ 跑出剩下 $k$ 个 $\verb!swap!$ 操作，输出答案。

出题者题解

代码（Code）

30分

#include<bits/stdc++.h> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,n) cerr<<a[i]<<b;cerr<<'\n';}
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;double Tim;

struct BIT{
	int c[N],n;inline void init(int x){n=x;memset(c,0,sizeof c);}
	inline int lbt(int x){return x&-x;}
	void update(int x,int k){for(int i=x;i<=n;i+=lbt(i))c[i]+=k;}
	int ask(int x){int res=0;for(int i=x;i;i-=lbt(i))res+=c[i];return res;}
	inline int ask(int l,int r){return ask(r)-ask(l-1);}
}B; 

int a[N];
int n,k;

void Solve(){
	n=rd(),k=rd(),B.init(n);
	int res=0;For(i,1,n){
		a[i]=rd();
		res += B.ask(a[i]+1,n);
		B.update(a[i], 1);
	}if(res<k) return puts("Impossible!"),void();
	
	res = 0;
	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]), res++;
			if(res==k){
				For(i,1,n) write(a[i]),putchar(' ');
				return;
			}
		}
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	int Tt=1;Tim=clock();
	while(Tt--) Solve();
	return cerr<<"\nTIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}

100分

#include<bits/stdc++.h> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a) {For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n';}
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool d=false;while(!isdigit(c=getchar()))d=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return d?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;double Tim;

struct BIT{
	int c[N],n;inline void init(int x){n=x;memset(c,0,sizeof c);}
	inline int lbt(int x){return x&-x;}
	void update(int x,int k){for(int i=x;i<=n;i+=lbt(i))c[i]+=k;}
	int ask(int x){int res=0;for(int i=x;i;i-=lbt(i))res+=c[i];return res;}
	inline int ask(int l,int r){return ask(r)-ask(l-1);}
}B; 

int a[N],b[N],d[N];
int n,k,level;

void Erfen(){
	int l=0,r=n,mid,res=-1,kleft=-1;
	auto check = [&](auto mid)->int{
		int res = 0;
		For(i,1,n) res += min(d[i], mid);
		return res;
	};
	while(l<=r){
		mid = (l+r)>>1;
		int tmp = check(mid);
		if(tmp <= k) l=mid+1, res=mid, kleft=k-tmp;
		else r = mid-1;
	}tie(level,k) = tie(res,kleft);
}

bitset<N> vst;
void Solve(){
	n=rd(),k=rd(),B.init(n);
	int res=0;For(i,1,n){
		a[i] = rd();
		res += d[i]=B.ask(a[i]+1,n);
		B.update(a[i], 1);
	}if(res<k) return puts("Impossible!"),void();
	
	Erfen();
	
	For(i,1,n) if(d[i] >= level) b[i-level] = a[i], vst[a[i]] = true;
	for(int i=1,j=1;i<=n;i++){
		if(b[i]) continue;
		while(vst[j]) j++;
		vst[j]=true, b[i]=j;
	}
	
	for(int j=1;j<=n-level;j++){
		if(k==0) break; 
		if(b[j]>b[j+1]) swap(b[j],b[j+1]), k--;
	}
	For(i,1,n) write(b[i]), putchar(" \n"[i==n]);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	int Tt=1;Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}