题目内容

塔子哥是一名摄影师，他刚刚拍摄了一组照片，但是由于光线等原因，照片的整体色调偏暗。他想要将每个像素点的亮度值都加上一个适当的值，来提高整张照片的亮度。同时，他希望加上的值不会使照片的亮度变得过于明亮或过于昏暗，而是尽可能地接近中间值 128。

给定一个长度为 $n$ 的数组 $img$，表示一张图像的 $n$ 个像素点，每个像素点的取值范围为 $[0, 255]$ 的正整数。塔子哥需要找到一个整数 $k$，将数组 $img$ 中的每个元素都加上 $k$，得到一个新的数组 $newImg$，使得 $newImg$ 的所有像素的平均值最接近中位值 128。最后，输出这个整数 $k$。

输入描述

输入 $n$ 个整数，中间用空格分隔。

$1\le n \le 100$

输出描述

输出满足条件的 $k$ 。

如果有多个满足条件的k输出最小的那个

注意： 新图的像素值会自动截取到 $[0,255]$ 范围，如，当像素点值 $<0$ 是，其值会自动更新为 $0$ 。

样例

样例一

输入

0 0 0 0

输出

128

样例二

输入

129 130 129 130

输出

-2

样例解释

$-1$ 的均值 $128.5$ , $-2$ 的均值为 $127.5$ ，输出较小的数 $-2$

思路分析

题目要求找到一个整数 k，将所有像素点的亮度值都加上 k 后，使得新数组 newImg 的平均亮度值尽可能接近 128。我们可以通过遍历 k 的可能值，从 -255 到 255，逐一测试找到最优解。

对于每一个可能的 k 值：

1. 加法运算：将每个像素值都加上 k。
2. 截断处理：如果新的亮度值低于 0，则将其设为 0；如果高于 255，则设为 255，以确保像素值保持在有效范围内。
3. 计算平均值：对每个经过处理的像素值求和并计算新图像 newImg 的平均值。
4. 求解最优解：与目标值 128 的差值最小的 k 即为最优解。如果有多个 k 值满足条件，则取较小的那个。

算法流程

1. 遍历所有可能的 k 值：在范围 [-255, 255] 中枚举 k 的每一个值。
2. 计算 newImg：对 img 数组中的每个元素 i 加上 k，并将结果限制在 [0, 255] 的范围内。
3. 计算与目标值的差距：计算所有元素的和，除以元素个数以得到平均值，与 128 的绝对差值最小的 k 即为答案。
4. 更新结果：如果当前的绝对差值比之前的最小差值小，则更新结果 k。

时间复杂度

对于给定的数据范围 ( n <= 100 )：

• 枚举 k 的所有值，共 (511) 个（范围 [-255, 255]）。
• 对每个 k，需要遍历一次数组 ( img ) 进行求和，复杂度为 (O(n))。

因此，算法的时间复杂度为 (O(n + 511) = O(n))，可在线性时间内完成。

代码

Python代码

def get(x):		#由计算结果得到实际结果
	if x < 0:
		return 0
	if x > 255:
		return 255
	return x

img = list(map(int, input().split()))	#输入img数组
res, mi = 0, float('inf')			#初始化最小值为正无穷
for i in range(-255, 256):
	avage = sum([get(j+i) for j in img])	#计算平均值
	now = abs(avage  - 128*len(img))		#得到和128的距离
	if now < mi:		#如果比最小值小
		res, mi = i, now	#就更新答案
print(res)	#输出最终答案

C++代码

#include <iostream>
using namespace std;

int get(int x){
    if (x<0)
        return 0;
    if (x>255)
        return 255;
    return x;
}
int a[105];
int main()
{
    int cnt=0;
    while(cin>>a[cnt]) {
        cnt++;
    }
    int res=0,mi=100000000;
    for (int i=-255;i<=255;i++){
        int sum=0;
        for (int j=0;j<cnt;j++)
            sum+=get(a[j]+i);
        int now=abs(sum-128*cnt);
        if (now<mi)
        {
            mi=now;
            res=i;
        }
    }
    cout<<res<<endl;
    return 0;
}

Java代码

import java.io.Console;
import java.util.Scanner;

class Main {
    public static int get(int x) {
        if (x < 0)
            return 0;
        if (x > 255)
            return 255;
        return x;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cnt = 0;
        int[] a = new int[105];
        while (scanner.hasNext()) {
            a[cnt] = scanner.nextInt();
            cnt++;
        }
        int res = 0, mi = 100000000;
        for (int i = -255; i <= 255; i++) {
            int sum = 0;
            for (int j = 0; j < cnt; j++)
                sum += get(a[j] + i);
            int now = Math.abs(sum - 128 * cnt);
            if (now < mi) {
                mi = now;
                res = i;
            }
        }
        System.out.println(res);
    }
}

Js代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';

process.stdin.on('data', (data) => {
	input += data;
	return;
});
process.stdin.on('end', () => {
    function get(x) {
        if (x < 0)
            return 0;
        if (x > 255)
            return 255;
        return x;
    }
    input=input.split('\n');
    let a=input[0].split(' ');
    let cnt=a.length;
    for (let i=0;i<cnt;i++)
        a[i]=Number(a[i]);
    let res = 0, mi = 100000000;
    for (let i = -255; i <= 255; i++) {
        let sum = 0;
        for (let j = 0; j < cnt; j++)
            sum += get(a[j] + i);
        let now = Math.abs(sum - 128 * cnt);
        if (now < mi) {
            mi = now;
            res = i;
        }
    }
    console.log(res);
})