蓝桥杯备赛-拔河

问题描述

小明是学校里的一名老师，他带的班级共有 nn 名同学，第 ii 名同学力量值为 aiai​。在闲暇之余，小明决定在班级里组织一场拔河比赛。

为了保证比赛的双方实力尽可能相近，需要在这 nn 名同学中挑选出两个队伍，队伍内的同学编号连续：{al1,al1+1,…,ar1−1,ar1}{al1​​,al1​+1​,…,ar1​−1​,ar1​​} 和 {al2,al2+1,…,ar2−1,ar2}{al2​​,al2​+1​,…,ar2​−1​,ar2​​}，其中 l1≤r1<l2≤r2l1​≤r1​<l2​≤r2​。

两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

输入格式

输入共两行。

第一行为一个正整数 nn。

第二行为 nn 个正整数 aiai​。

输出格式

输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。

样例输入

5
10 9 8 12 14

样例输出

1

样例说明

其中一种最优选择方式：

队伍 1： {a1,a2,a3}{a1​,a2​,a3​}，队伍 2：{a4,a5}{a4​,a5​}，力量值和分别为 10+9+8=2710+9+8=27 , 12+14=2612+14=26，差距为 ∣27−26∣=1∣27−26∣=1 。

评测用例规模与约定

对于 20%20% 的评测用例，保证 n≤50n≤50 。

对于 100%100% 的评测用例，保证 n≤103,ai≤109n≤103,ai​≤109 。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//计算两个子数组的最小差值，前缀和
typedef long long LL;
typedef pair<LL, pair<int, int>> PIII; // 存储子数组和、起始位置和结束位置
const int N = 1050;

LL s[N], a[N];

int main() {
    int n;
    cin >> n;
    vector<PIII> v;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i]; // 计算前缀和
    }
    // 计算所有子数组和及其起始和结束位置
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            v.push_back({s[j] - s[i - 1], {i, j}}); // 存储子数组和、起始位置和结束位置
        }
    }
    // 按子数组和排序
    sort(v.begin(), v.end());//元素是piar时，默认字典序排列分别比较第一个，第二个等
    LL ans = 1e18;
    for (int i = 0; i < v.size() - 1; i++) 
    //子数组已经按照大小排列，只需要依次计算相邻的子数组的差值即可并进行比较
    {
            // 检查两个子数组是否不相交
            if (v[i].second.second < v[i+1].second.first || v[i+1].second.second < v[i].second.first) {
                ans = min(ans, abs(v[i+1].first - v[i].first));
            }
    }
    cout << ans << endl;
    return 0;
}