问题描述
小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学的力量值为 a_i。
在闲暇之余，小明决定在班级里组织一场拔河比赛。
为了保证比赛双方实力尽可能接近，需要在这 n 名同学中挑选出两个队伍：
-
每个队伍内的同学编号连续，分别为：
{a_l1, a_l1+1, ..., a_r1} {a_l2, a_l2+1, ..., a_r2} -
满足：
l1 ≤ r1 < l2 ≤ r2
两个队伍的人数不必相同，但希望这两个队伍中同学们的力量值之和尽可能接近。
请计算出力量值之和差距最小的挑选方式。
输入格式
共两行：
- 第一行为一个正整数
n； - 第二行为
n个正整数a_i，表示每位同学的力量值。
输出格式
输出一行，一个非负整数，表示两个队伍力量值之和的最小差距。
样例输入
5
10 9 8 12 14
样例输出
1
样例说明
一种最优选择方式为：
- 队伍 1：
{a_1, a_2, a_3} = {10, 9, 8}，总和为27 - 队伍 2：
{a_4, a_5} = {12, 14}，总和为26
差值为 |27 - 26| = 1
评测用例规模与约定
- 对于 20% 的评测用例，
n ≤ 50 - 对于 100% 的评测用例，
n ≤ 1000，每个a_i ≤ 10^9
c++代码
#include<bits/stdc++.h>
#include<stdio.h>using namespace std;typedef long long ll;ll n;
vector<ll> arr, sum_pre;int main() {scanf("%lld", &n);arr = vector<ll>(n + 1, 0);sum_pre = vector<ll>(n + 1, 0);ll ans = LONG_MAX;for (ll i = 1; i <= n; i++) {scanf("%lld", &arr[i]);sum_pre[i] = arr[i] + sum_pre[i - 1];}for (ll i = 1; i <= n; i++) {for (ll j = i; j <= n; j++) {ll k = j + 1, w = j + 1, p1 = sum_pre[j] - sum_pre[i - 1];ll mid;while(w <= n && k <= w) {mid = sum_pre[w] - sum_pre[k - 1];ans = min(ans, abs(p1 - mid));if (mid > p1) k++;if (mid < p1) w++;if (mid == p1) {printf("0");return 0;}}}}printf("%lld", ans);return 0;
}//by wqs
算法思路
不要误以为每个人都要上场，这道题目可以选择让一些人不上场的。
我把他理解为四指针，当然有人说他是双指针也是对的，不同的说法罢了。
i, j两个指针确定第一个队伍的区间,这里只能暴力确定
for (ll i = 1; i <= n; i++) {for (ll j = i; j <= n; j++) {//第一个队伍被确立为[i, j]}
}
w和n两个指针,确立第二个区间，第二个区间不能暴力确立，否则超时
这个问题本质上是在j + 1后面找一个区间使得这个区间的和与某个数最接近，至于这个数就是第一个区间里面的区间和p1。
这样写，时间复杂度为o(n);
ll k = j + 1, w = j + 1, p1 = sum_pre[j] - sum_pre[i - 1];
ll mid;
while(w <= n && k <= w) {mid = sum_pre[w] - sum_pre[k - 1];ans = min(ans, abs(p1 - mid));if (mid > p1) k++;//不考虑w++，因为这样只会让mid越来越比p1大if (mid < p1) w++;//不考虑k++，我们这样只会让mid越来越比p1小if (mid == p1) {printf("0");return 0;}
}
