算法设计与分析 2.5 Joyvan的难题（曼哈顿距离、空间最小

题目描述：

Joyvan最近遇到了一个难题,对于一个包含N个整数的序列a1,a2,……,aN，定义：

现在Joyvan想要你帮他计算所有f（i，j） (1<=i<j<=N)的最小值。

输入格式：

输入的第一行为数字N，表示给定序列的长度。

第二行包含N个整数，表示序列中的整数a1,a2,……,aN。

对于80%的数据，N<=1000。

对于100%的数据，N<=100000，序列中的整数绝对值不大于10000。

输出格式：

输出一个整数，即所有f(i，j) (1<=i<j<=N)的最小值。

样例输入：

4
1 0 0 -1

样例输出：

1

解法一：

暴力解，直接把所有的f（i，j）计算出来，再用一个min值动态记录最小值，最后输出min。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 100000;

int a[N];

long f(int i, int j) {
    long ans1 = j - i;
    long ans2 = 0;
    for (i; i <= j - 1; i++) {
        ans2 = ans2 + a[i];
    }
    long ans = ans1 * ans1 + ans2 * ans2;
    return ans;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    long min = f(1, 2);
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++)
            if (f(i, j) < min)
                min = f(i, j);
    }
    cout << min;
}

由于数字很大，第一次数据溢出了只有1分，后来改进后成绩是8分（虽然已经提交的最后期限，最后成绩还是1分），也算吃一堑长一智吧。

最后两个点，用暴力解法会超时，后续会研究满分解法。

解法二：

因为大佬们一眼就看出来了，其实这是一个计算曼哈顿距离的式子，也就是一个求最小空间点对的问题。

这才是这一题出题人想要的正解，空间点对问题网上代码很多，有兴趣的同学可以找出来研究研究。

贴一张大佬同学的代码，可以参考。