K-Knowledge Test about Match
原题链接：https://ac.nowcoder.com/acm/contest/11166/K
文章目录
- K-Knowledge Test about Match
-
- 题目大意
- 题目思路
- 代码实现
- 总结
题目大意
给定两个长度为 n n n的数组： a = { 0 , 1 , 2 , ? ? ? ， n ? 1 } a=\{0,1,2,···，n-1\} a={ 0,1,2,???，n?1} b = { a 1 , a 2 , a 3 , ? ? ? ， a n ? 1 } b=\{a_1,a_2,a_3,···，a_{n-1}\} b={ a1?,a2?,a3?,???，an?1?}现在你可以任意调整数组 b b b中的元素顺序，使得它们的loss函数最小。
定义数组 a a a与数组 b b b的loss函数为： f ( a , b ) = ∑ i = 0 n ? 1 ∣ a i ? b i ∣ f(a,b)=\sum\limits_{i=0}^{n-1}\sqrt{\left|a_i-b_i\right|} f(a,b)=i=0∑n?1?∣ai??bi?∣?由于解决这个问题的时间有限，所以只要求出近似值即可。
共 T T T组数据，设第 k k k组数据的答案的loss函数为 f k ? f_k^* fk??,你的输出结果的loss函数为 f k ^ f_k\hat{} fk?^,则只需满足一下不等式即可： 1 T = ∑ k = 1 T f k ^ ? f k ? f k ? ≤ 4 \frac{1}{T}=\sum\limits_{k=1}^{T}\frac{f_k\hat{}-f_k^*}{f_k^*}\le4% T1?=k=1∑T?fk??fk?^?fk???≤4
题目思路
很容易可以看出多个数偏移很少比几个数偏移很多更好，所以枚举偏移的值，从0枚举到n-1，即可。
代码实现
#include<bits/stdc++.h>
using namespace std;
int n,t,a[10001],b[100001];
int main() {
cin>>t;while(t--){
memset(a,-1,sizeof(a));memset(b,0,sizeof(b));scanf("%d",&n);for(int i=0;i<n;i++){
int x;scanf("%d",&x),b[x]++;}for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(b[j]!=0){
if(b[j]>0 && j+i<n && a[j+i]==-1){
a[j+i]=j;b[j]--;}if(b[j]>0 && j-i>=0 && a[j-i]==-1){
a[j-i]=j;b[j]--;}}for(int i=0;i<n;i++)printf("%d ",a[i]);puts("");}
}
总结
什么也没有