题目描述
给定一个长度为 n 的正整数数组 a1,a2,…,an。
你可以任意改变其中任意元素的值。
但是,改变后的元素的值仍需是正整数。
将一个元素的值从 a 变为 b 所需要付出的代价为 |a−b|。
对于一个正整数 t,如果 |ai−t|≤1,则称第 i 个元素能够与 t 匹配。
现在,请你指定一个正整数 t,并且用最小的代价修改整个数组,使得数组中所有元素都能够与 t 匹配。
指定的 t 不同,所需付出的最小代价也可能不同。
请你合理选择正整数 t,目标是让所需付出的最小代价尽可能小。
样例
2
3
10 1 4
5
1 1 2 2 3
3 7
2 0
算法
枚举暴力
直接暴力枚举
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int T, n;
int a[N];
int main(){
scanf("%d", &T);
while (T--){
scanf("%d", &n);
int sum = 0;
int x = -1e9;
for (int i=1;i<=n;i++) {
scanf("%d", &a[i]);
sum += a[i];
x = max(x, a[i]);
}
int k = sum / n;
int res = 0;
int cnt = 1e9;
int u = 0;
for (int i=0;i<=x;i++){
res = 0;
for (int j=1;j<=n;j++){
int b = i - 1, c = i + 1;
if (a[j]==i||a[j]==b||a[j]==c){
continue;
}else{
int t = min(abs(a[j]-b), abs(a[j]-c));
res += t;
}
}
// cout <<res << endl;
if (cnt>res){
u = i;
cnt = res;
}
}
printf("%d %d\n", u, cnt);
}
return 0;
}