思路：贪心

对每一个点考虑两种情况，乘以-1和不乘以-1

对于第$i$个点，对应的最小值为$min(abs(a[i] - b[i]) , abs(a[i] + b[i]))$

然后对这两种情况取最小值，累加所有的答案即可。

时间复杂度

$O(n)$

c++代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 1e5 + 5;
int a[maxn] , b[maxn];
ll pre[maxn] , aft[maxn];
int main (){
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++){
        cin >> a[i];
    }
    for (int i = 1 ; i <= n ; i++){
        cin >> b[i];
    }
    for (int i = 1 ; i <= n ; i++){
        pre[i] = pre[i - 1] + min(abs(a[i] - b[i]) , abs(a[i] + b[i]));
    }
    cout << pre[n] << endl;
}

python代码

n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
ans = 0
for i in range(n):
    cur = float('inf')
    for x in [-1, 1]:
        for y in [-1, 1]:
            cur = min(cur, abs(a[i] * x - b[i] * y))
    ans += cur
print(ans)

Java代码

import java.util.*;

class Main {
    public static void main(String[]args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a  = new int[n];
        for (int i = 0 ; i < n ; i++) a[i] = sc.nextInt();

        for (int i = 0 ; i < n ; i++) {
            if (a[i] == -1) {
                int p1 = i-1, p2 = i+1;
                int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
                while (p1 >= 0) {
                    min1 = Math.min(min1, a[p1--]);
                }
                while (p2 < n) {
                    min2 = Math.min(min2, a[p2++]);
                }
                System.out.println(min1 + min2);
                return;
            }
        }

    }
}

题目描述

小红周末去爬山，突然心血来潮要做一个爬山模拟器。

模拟器会随机生成 $n$ 个出发点的海拔$aᵢ$,，以及从这些点到达对应的山顶的海拔$bᵢ$。

现在定义总距离为： $∑_{i=1}^{n}=|a_i−b_i|$，另外小红还增加了一个VIP修改功能，可以进行任意次操作： 选择任意一个点的海拔，使其乘以 $-1$。

现在小红测试的时候充了一个VIP，他想使最终的总距离尽可能小，你能求出这个值吗？

输入描述

第一行输入一个正整数$n$， 代表两个数组的长度。 第二行输入$n$个整数$aᵢ$,代表第一个数组。 第三行输入$n$个整数$bᵢ$,代表第二个数组。

$1≤n≤10⁵,−10⁹≤aᵢ,bᵢ≤10⁹$

输出描述

一个整数，代表两个数组的最小距离。

样例

样例输入

3
1 2 3
-1 -2 -3

样例输出

0

说明 第一个数组变成[-1,-2,-3]即可。