#P1581. 2022.11.27-秋招-平均像素值
-
ID: 26
Tried: 431
Accepted: 86
Difficulty: 3
2022.11.27-秋招-平均像素值
题目内容
塔子哥是一名摄影师，他刚刚拍摄了一组照片，但是由于光线等原因，照片的整体色调偏暗。他想要将每个像素点的亮度值都加上一个适当的值，来提高整张照片的亮度。同时，他希望加上的值不会使照片的亮度变得过于明亮或过于昏暗，而是尽可能地接近中间值 128。
给定一个长度为 n 的数组 img，表示一张图像的 n 个像素点，每个像素点的取值范围为 [0,255] 的正整数。塔子哥需要找到一个整数 k，将数组 img 中的每个元素都加上 k，得到一个新的数组 newImg，使得 newImg 的所有像素的平均值最接近中位值 128。最后，输出这个整数 k。
输入描述
输入 n 个整数，中间用空格分隔。
1≤n≤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 值：
- 加法运算：将每个像素值都加上
k。 - 截断处理：如果新的亮度值低于
0，则将其设为0；如果高于255，则设为255，以确保像素值保持在有效范围内。 - 计算平均值：对每个经过处理的像素值求和并计算新图像
newImg的平均值。 - 求解最优解：与目标值
128的差值最小的k即为最优解。如果有多个k值满足条件，则取较小的那个。
算法流程
- 遍历所有可能的
k值：在范围[-255, 255]中枚举k的每一个值。 - 计算
newImg：对img数组中的每个元素i加上k，并将结果限制在[0, 255]的范围内。 - 计算与目标值的差距：计算所有元素的和，除以元素个数以得到平均值，与
128的绝对差值最小的k即为答案。 - 更新结果：如果当前的绝对差值比之前的最小差值小，则更新结果
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);
})