蓝桥杯备赛-拔河
问题描述
小明是学校里的一名老师，他带的班级共有 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;
}