题意:数组a={0,1,2…n-1},现在给定一个数组b,你可以随意交换b中的元素,定义损失函数f(a,b)= ∑ 1 n \sum_1^n ∑1n a b s ( a i − b i ) \sqrt{abs(ai-bi)} abs(ai−bi) ,要求你交换后的b数组与a数组的损失函数和最小损失函数在T组的平均偏差小于0.04
这题不会验证做法的正确性,但还是来讲下蒟蒻补题思路:暴力的去不断地减小损失函数,循环拿出i,j两个位置的b,如果 ( a b s ( b i − i ) ) \sqrt{(abs(bi-i))} (abs(bi−i)) + ( a b s ( b j − j ) ) \sqrt{(abs(bj-j))} (abs(bj−j)) > ( a b s ( b i − j ) ) \sqrt{(abs(bi-j))} (abs(bi−j)) + ( a b s ( b j − i ) ) \sqrt{(abs(bj-i))} (abs(bj−i)) 的话就交换ai,bj,只遍历一次时间为O(n*n),为了保证正确性,自然要尽可能的多的重复遍历(然而测了一下只要遍历次数大于2次就能过),由于 ∑ 1 n \sum_1^n ∑1nn<=40000,每一次n<=1000,所以n=1000至多40次,此时时间复杂度大约为1e7级别,可以选择10次左右
AcCode
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 1e4 + 100;
double sqt[N];
int arr[N];
inline void init() { for (int i = 1; i < N-10; i++) sqt[i] = sqrt((double)i); }
inline int abs(int x, int y) { return (x > y) ? (x - y) : (y - x); }
inline double S(int x, int y) { return sqt[abs(x - y)]; }
signed main() {
init();
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
int maxup = 10;
for (int k = 1; k <=maxup ; k++) {
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if ((S(arr[i], (i-1)) + S(arr[j], (j-1))) > (S(arr[i], (j-1)) + S(arr[j], (i-1)))) {
swap(arr[i], arr[j]);
}
}
}
}
for (int i = 1; i <= n; i++) printf("%d ", arr[i]);
printf("\n");
}
}