AcWing 3809. 修改数组

原题链接

题目描述

给定一个长度为 $n$ 的正整数数组 $a_1,a_2,…,a_n$ 。

你可以任意改变其中任意元素的值。

但是，改变后的元素的值仍需是正整数。

将一个元素的值从 $a$ 变为 $b$ 所需要付出的代价为 $|a-b|$ 。

对于一个正整数 $t$ ，如果 $|a_i-t|≤1$ ，则称第 ii 个元素能够与 $t$ 匹配。

现在，请你指定一个正整数 $t$ ，并且用最小的代价修改整个数组，使得数组中所有元素都能够与 $t$ 匹配。

指定的 $t$ 不同，所需付出的最小代价也可能不同。

请你合理选择正整数 $t$ ，目标是让所需付出的最小代价尽可能小。

输入格式

第一行包含整数 $T$ ，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $n$ 。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$ 。

输出格式

每组数据输出一行结果，首先输出你选择的正整数 $t$ ，然后输出使得数组中所有元素都能够与 $t$ 匹配，所需付出的最小代价。

如果 $t$ 有多种合理选择，则任选其一输出即可。

数据范围

$1≤T≤20$ , $1≤n≤1000$ , $1≤a_i≤100$ , 同一测试点内所有 $n$ 的和不超过 $1000$ 。

样例

输入样例：

输出样例：

3 7
2 0

思路

要让所有元素与 $t$ 匹配， $t$ 一点在 $a_i$ 的范围内。

由于 $a_i$ 不大，枚举每一个 $t$ ，计算最小代价。

代码

C++

#include <iostream>

using namespace std;

const int N = 1005;
int a[N];

int main()
{
    int T;
    cin >> T;
    while ( T-- )
    {
        int n;
        scanf("%d", &n);
        for ( int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
        int res = 0, cnt = 1e9;
        for ( int t = 1; t <= 100; t ++ )
        {
            int k = 0;
            for ( int i = 0; i < n; i ++ )
                k += (abs(a[i] - t) > 1 ? abs(a[i] - t) - 1 : 0);
            if ( k < cnt ) res = t, cnt = k;                
        }
        printf("%d %d\n", res, cnt);
    }
}

Java

import java.util.*;

public class Main
{
    static Scanner in = new Scanner(System.in);
    
    public static void main(String args[])
    {
        int T = in.nextInt();
        while ( T -- > 0 ) 
        {
            int n = in.nextInt();
            int a[] = new int[n];
            for ( int i = 0; i < n; i ++ ) a[i] = in.nextInt();
            int res = 0, cnt = (int) 1e9;
            for ( int t = 1; t <= 100; t ++ )
            {
                int k = 0;
                for ( int x : a )
                    k += Math.abs(x - t) > 1 ? Math.abs(x - t) - 1 : 0;
                if ( k < cnt )
                {
                    res = t;
                    cnt = k;
                }
            }
            System.out.printf("%d %d\n", res, cnt);
        }
    }
}