2023-09-05：请用go语言编写。一个图像有n个像素点，存储在一个长度为n的数组arr里，

每个像素点的取值范围[0,s]的整数，

请你给图像每个像素点值加上一个整数k（可以是负数），

像素值会自动截取到[0,s]范围，

当像素值<0，会更改为0，当新像素值>s，会更改为s，

这样就可以得到新的arr，想让所有像素点的平均值最接近中位值s/2, 向下取整。

请输出这个整数k, 如有多个整数k都满足, 输出小的那个。

1 <= n <= 10^6，

1 <= s <= 10^18。

来自华为OD。

来自左程云。

答案2023-09-05：

根据代码和题目描述，可以将算法分为以下三种不同的方法：

方法一：暴力方法

• 这种方法通过枚举k的值来计算每个像素值加上k后的平均值，然后选择平均值最接近中位值s/2的k。

• 该方法采用两层循环：外层循环枚举k的取值，内层循环计算平均值。

• 时间复杂度：O(n^2)

• 空间复杂度：O(1)

方法二：优化暴力方法

• 这种方法在暴力方法的基础上进行了一些优化，采用二分查找来减少计算的次数。

• 首先，确定k的取值范围为[-s, s]，然后进行二分查找来逼近平均值最接近中位值s/2的k。

• 时间复杂度：O(n*log(s))

• 空间复杂度：O(1)

方法三：正式方法（最优解）

• 这种方法是一种最优解，通过先对数组arr进行排序，然后使用前缀和数组pre来存储累加和，以便在计算过程中快速计算区间和。

• 确定k的取值范围，根据k的正负分别进行二分查找，得到最接近中位值s/2的k。

• 时间复杂度：O(nlog(n) + log(s)log(n))

• 空间复杂度：O(n)

go完整代码如下：

package main

import (
    "fmt"
    "math"
    "math/rand"
    "sort"
)

// 暴力方法
// 为了测试
func best1(arr []int, s int) int {
    half := s / 2
    average := -100000
    ans := -s
    for k := -s; k <= s; k++ {
        curAverage := average1(arr, k, s)
        if math.Abs(float64(half-curAverage)) < math.Abs(float64(half-average)) {
            average = curAverage
            ans = k
        }
    }
    return ans
}

// 暴力方法
// 为了测试
func average1(arr []int, k, s int) int {
    sum := 0
    for _, num := range arr {
        value := num + k
        if value < 0 {
            sum += 0
        } else if value > s {
            sum += s
        } else {
            sum += value
        }
    }
    return sum / len(arr)
}

// 优化了一下，但不是最优解
func best2(arr []int, s int) int {
    l := -s
    r := s
    m := 0
    half := s / 2
    average := -s
    ans := 0
    for l <= r {
        m = (l + r) / 2
        curAverage := average1(arr, m, s)
        if math.Abs(float64(half-curAverage)) < math.Abs(float64(half-average)) ||
            (math.Abs(float64(half-curAverage)) == math.Abs(float64(half-average)) && m < ans) {
            average = curAverage
            ans = m
        }
        if curAverage >= half {
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return ans
}

// 正式方法
// 最优解
// O(N * logN) + O(logS *  logN)
func best3(arr []int, s int) int {
    sort.Ints(arr)
    sum := make([]int, len(arr))
    sum[0] = arr[0]
    for i := 1; i < len(arr); i++ {
        sum[i] = sum[i-1] + arr[i]
    }
    l := -s
    r := s
    m := 0
    half := s / 2
    average := -s
    ans := 0
    for l <= r {
        m = (l + r) / 2
        curAverage := average3(arr, sum, m, s)
        if math.Abs(float64(half-curAverage)) < math.Abs(float64(half-average)) ||
            (math.Abs(float64(half-curAverage)) == math.Abs(float64(half-average)) && m < ans) {
            average = curAverage
            ans = m
        }
        if curAverage >= half {
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return ans
}

func average3(arr []int, pre []int, k, s int) int {
    n := len(arr)
    if k < 0 {
        l := bsZero(arr, k)
        sum := rangeSum(pre, l+1, n-1)
        return (sum + (k * (n - l - 1))) / n
    } else {
        r := bsS(arr, k, s)
        sum := rangeSum(pre, 0, r-1)
        return (sum + (k * r) + (s * (n - r))) / n
    }
}

func bsZero(arr []int, k int) int {
    ans := -1
    l := 0
    r := len(arr) - 1
    var m int
    for l <= r {
        m = (l + r) / 2
        if arr[m]+k <= 0 {
            ans = m
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return ans
}

func bsS(arr []int, k, s int) int {
    ans := len(arr)
    l := 0
    r := len(arr) - 1
    var m int
    for l <= r {
        m = (l + r) / 2
        if arr[m]+k >= s {
            ans = m
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return ans
}

func rangeSum(pre []int, l, r int) int {
    if l > r {
        return 0
    }
    if l == 0 {
        return pre[r]
    }
    return pre[r] - pre[l-1]
}

// 为了测试
func randomArray(n, s int) []int {
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = randInt(0, s)
    }
    return arr
}

func randInt(min, max int) int {
    return min + rand.Intn(max-min+1)
}

func main() {
    N := 50
    S := 500
    testTimes := 10000
    fmt.Println("测试开始")
    for i := 0; i < testTimes; i++ {
        n := randInt(1, N)
        s := randInt(1, S)
        arr := randomArray(n, s)
        ans1 := best1(arr, s)
        ans2 := best2(arr, s)
        ans3 := best3(arr, s)
        if ans1 != ans2 || ans1 != ans3 {
            fmt.Println("出错了！")
        }
    }
    fmt.Println("测试结束")
}

c++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int average1(vector<int>& arr, int k, int s);
int average3(vector<int>& arr, vector<int>& pre, int k, int s);
int bsZero(vector<int>& arr, int k);
int bsS(vector<int>& arr, int k, int s);
int rangeSum(vector<int>& pre, int l, int r);
int best1(vector<int>& arr, int s);
int best2(vector<int>& arr, int s);
int best3(vector<int>& arr, int s);
vector<int> randomArray(int n, int s);
void test();

int average1(vector<int>& arr, int k, int s) {
    int sum = 0;
    for (int num : arr) {
        int value = num + k;
        if (value < 0) {
            sum += 0;
        }
        else if (value > s) {
            sum += s;
        }
        else {
            sum += value;
        }
    }
    return sum / arr.size();
}

int average3(vector<int>& arr, vector<int>& pre, int k, int s) {
    int n = arr.size();
    if (k < 0) {
        int l = bsZero(arr, k);
        int sum = rangeSum(pre, l + 1, n - 1);
        return (sum + (k * (n - l - 1))) / n;
    }
    else {
        int r = bsS(arr, k, s);
        int sum = rangeSum(pre, 0, r - 1);
        return (sum + (k * r) + (s * (n - r))) / n;
    }
}

int bsZero(vector<int>& arr, int k) {
    int ans = -1;
    int l = 0;
    int r = arr.size() - 1;
    int m;
    while (l <= r) {
        m = (l + r) / 2;
        if (arr[m] + k <= 0) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
    return ans;
}

int bsS(vector<int>& arr, int k, int s) {
    int ans = arr.size();
    int l = 0;
    int r = arr.size() - 1;
    int m;
    while (l <= r) {
        m = (l + r) / 2;
        if (arr[m] + k >= s) {
            ans = m;
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}

int rangeSum(vector<int>& pre, int l, int r) {
    if (l > r) {
        return 0;
    }
    return l == 0 ? pre[r] : (pre[r] - pre[l - 1]);
}

int best1(vector<int>& arr, int s) {
    int half = s / 2;
    int average = -100000;
    int ans = -s;
    for (int k = -s; k <= s; k++) {
        int curAverage = average1(arr, k, s);
        if (abs(half - curAverage) < abs(half - average)) {
            average = curAverage;
            ans = k;
        }
    }
    return ans;
}

int best2(vector<int>& arr, int s) {
    int l = -s;
    int r = s;
    int m = 0;
    int half = s / 2;
    int average = -s;
    int ans = 0;
    while (l <= r) {
        m = (l + r) / 2;
        int curAverage = average1(arr, m, s);
        if ((abs(half - curAverage) < abs(half - average))
            || ((abs(half - curAverage) == abs(half - average)) && m < ans)) {
            average = curAverage;
            ans = m;
        }
        if (curAverage >= half) {
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}

int best3(vector<int>& arr, int s) {
    sort(arr.begin(), arr.end());
    vector<int> sum(arr.size());
    sum[0] = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        sum[i] = sum[i - 1] + arr[i];
    }
    int l = -s;
    int r = s;
    int m = 0;
    int half = s / 2;
    int average = -s;
    int ans = 0;
    while (l <= r) {
        m = (l + r) / 2;
        int curAverage = average3(arr, sum, m, s);
        if ((abs(half - curAverage) < abs(half - average))
            || ((abs(half - curAverage) == abs(half - average)) && m < ans)) {
            average = curAverage;
            ans = m;
        }
        if (curAverage >= half) {
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}

vector<int> randomArray(int n, int s) {
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % (s + 1);
    }
    return arr;
}

void test() {
    int N = 50;
    int S = 500;
    int testTimes = 10000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTimes; i++) {
        int n = rand() % N + 1;
        int s = rand() % S + 1;
        vector<int> arr = randomArray(n, s);
        int ans1 = best1(arr, s);
        int ans2 = best2(arr, s);
        int ans3 = best3(arr, s);
        if (ans1 != ans2 || ans1 != ans3) {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;
}

int main() {
    test();
    return 0;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接