2022.11.27-秋招-平均像素值

XiangChao LV 3 @ 7 months ago

img = list(map(int, input().split()))
n = len(img)
k = -1
ave = -1
for i in range(-127, 129, 1):
    tmp = 0
    for num in img:
        if num + i < 0:
            tmp += 0
        elif num + i > 255:
            tmp += 255
        else:
            tmp += (num + i)
    tmp_ave = tmp / n
    if abs(128 - tmp_ave) < abs(128 - ave):
        ave = tmp_ave
        k = i 
print(k)

ichbinbobobo LV 7 @ 9 months ago

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    int num;
    vector<int> arr;
    int sum = 0;
    int count = 0;
    while(cin>>num)
    {
        arr.push_back(num);
        sum+=num;
        count++;
    }

    int index =0;
    float shift = (128-float(sum)/count);
    if(shift>0)
    {
        index = shift-floor(shift)>0.5?ceil(shift):floor(shift);  
    }
    if(shift<0)
    {
        index = shift-floor(shift)<0.5?ceil(shift):floor(shift);
    }
    if(abs(shift-floor(shift)-0.5)<1e-6)
        index = min(floor(shift), ceil(shift));
    cout << index << endl;
}

直接按照平均值和128的差来计算，因为目的肯定是使方差最小，方差一求导数就剩下和平均值的差异。

TaZi SU @ 9 months ago

思路分析

题目要求找到一个整数 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);
})

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

模拟

# Submissions

431

Accepted

Uploaded By

TaZi

3 solutions

思路分析

算法流程

时间复杂度

代码

Information

Status

Development

Support