蓝桥云客 拔河

1.拔河 - 蓝桥云课

问题描述

小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学力量值为 ai​。在闲暇之余，小明决定在班级里组织一场拔河比赛。为了保证比赛的双方实力尽可能相近，需要在这 n 名同学中挑选出两个队伍，队伍内的同学编号连续：{a1​,ai+1​,…,ar1​​} 和 {al2​​,al2​+1​,…,ar2​−1​,ar2​​}，其中 l1​≤r1​<l2​≤r2​。

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

输入格式

输入共两行。

第一行为一个正整数 n。

第二行为 n 个正整数 ai​。

输出格式

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

样例输入

5
10 9 8 12 14

样例输出

1

样例说明

其中一种最优选择方式：

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

评测用例规模与约定

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

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

思路：

1.题目没有说一定要选完全部人
2.重复的如何处理
3.并且保证队伍一个在左一个在右

代码如下：

#include <iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll; 
const ll L = 1e3+10;
ll a[L],pre[L];
vector <ll> num;
ll n,ans = 1e10;
int main()
{cin >> n;for(ll i = 1 ; i <= n ; i++){cin >> a[i];pre[i] = pre[i-1] + a[i];}for(ll i = 1 ; i <= n ; i++)//把所有区间的集合存进数组 {for(ll j = i ; j <= n ; j++){ll t = abs(pre[j] - pre[i-1]);if(t == pre[n])continue;
//		cout <<t << " ";num.push_back(t);} }sort(num.begin(),num.end());//排序，单调递增 for(ll i = 0 ; i < num.size() - 1 ; i++){ans = min(ans,abs(num[i] - num[i + 1])); }cout << ans;return 0;
}