2021牛客暑期多校训练营1-Knowledge Test about Match

题目链接

题意:数组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 ∑1n​n<=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");

	}
}
上一篇:IP SOC与Camera ISP


下一篇:【没有哪个港口是永远的停留~ 论文简读】Relational Knowledge Distillation