【思维】2021牛客暑期多校训练营1 K Knowledge Test about Match

题链

题目解析

因为要使权值最小，冒泡排序根据交换 $i,j$ 位置的值能否使整体更小来排序。
其中权值的计算一定要加上根号（如果不加就是直接递增排序一次冒泡后数组就不改变了，加根号后第二次冒泡排序时数组可能还会改变）。
跑 $3-5$ 次冒泡就能跑出来。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define eps 1e-3
#define MAXN 1e9
#define MS 1000009
#define mod 1000000007
#define B1 131
#define B2 13331

LL n,m,k;
LL p[MS];
double val[MS];

void init(){
	for(int i=0;i<=10000;i++) val[i] = sqrt(i);
}

void Bubble_sort(){
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(val[abs(p[i]-i)]+val[abs(p[j]-j)] > val[abs(p[i]-j)]+val[abs(p[j]-i)]){
				swap(p[i],p[j]);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	init();
	int ce;
	cin >> ce;
	while(ce--){
		cin >> n;
		for(int i=0;i<n;i++){
			cin >> p[i];
		}
		random_shuffle(p,p+n);
		for(int i=0;i<3;i++){
			Bubble_sort();
		}
		for(int i=0;i<n;i++){
			cout << p[i] << " ";
		}
		cout << "\n";
	}
	
	
	
	return 0;
}