[蓝桥杯 2024 省 B] 拔河
题目描述
小明是学校里的一名老师,他带的班级共有 \(n\) 名同学,第 \(i\) 名同学力量值为 \(a_i\)。在闲暇之余,小明决定在班级里组织一场拔河比赛。
为了保证比赛的双方实力尽可能相近,需要在这 \(n\) 名同学中挑选出两个队伍,队伍内的同学编号连续 \(\{{a_{l_1}}, a_{l_1 + 1}, \dots, a_{r_1 - 1}, a_{r_1}\}\) 和 \(\{{a_{l_2}}, a_{l_2 + 1}, \dots, a_{r_2 - 1}, a_{r_2}\}\),其中 \(l_1 \le r_1<l_2 \le r_2\)。
两个队伍的人数不必相同,但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。
输入格式
输入共两行。
第一行为一个正整数 \(n\)。
第二行为 \(n\) 个正整数 \(a_1, a_2, \dots a_n\)。
输出格式
输出共一行,一个非负整数,表示两个队伍力量值之和的最小差距。
样例 #1
样例输入 #1
5
10 9 8 12 14
样例输出 #1
1
提示
样例 1 解释
其中一种最优选择方式:
队伍 1:\(\{a_1, a_2, a_3\}\),队伍 2:\(\{a_4, a_5\}\),力量值和分别为 \(10 + 9 + 8 = 27\),\(12 + 14 = 26\),差距为 \(|27 − 26| = 1\)。
数据规模与约定
- 对 \(20\%\) 的数据,\(n \leq 50\)。
- 对全部的测试数据,保证 \(1 \leq n \leq 10^3\),\(1 \leq a_i \leq 10^9\)。
解法:
把所有以i(\(1 \leq i \leq n\))开头的区间暴力出来,进行排序,因为要找最小差值,排序后,相邻的一定是差最小的,所以按每个区间的值从小到大排序,然后对相邻区间取差值找最小差值。
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int N=1010;
int n,a[N],s[N],res=1e18;
vector<pii>v;
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
v.push_back({s[j]-s[i],i});
}
}
sort(v.begin(),v.end());
for(int i=0;i<v.size()-1;i++)
{
res=min(res,v[i+1].first-v[i].first);
}
printf("%lld",res);
return 0;
}
标签:2024,10,题解,样例,蓝桥,leq,队伍
From: https://www.cnblogs.com/watasky/p/18176988