【二分查找 前缀和】P10429 [蓝桥杯 2024 省 B] 拔河|普及+

本文涉及的基础知识点

本博文代码打包下载
C++二分查找
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

[蓝桥杯 2024 省 B] 拔河

题目描述

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

为了保证比赛的双方实力尽可能相近，需要在这 $n$ 名同学中挑选出两个队伍，队伍内的同学编号连续 { a l 1 , a l 1 + 1 , … , a r 1 − 1 , a r 1 } \{{a_{l_1}}, a_{l_1 + 1}, \dots, a_{r_1 - 1}, a_{r_1}\} {al1​​,al1​+1​,…,ar1​−1​,ar1​​} 和 { a l 2 , a l 2 + 1 , … , a r 2 − 1 , a r 2 } \{{a_{l_2}}, a_{l_2 + 1}, \dots, a_{r_2 - 1}, a_{r_2}\} {al2​​,al2​+1​,…,ar2​−1​,ar2​​}，其中 $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 } \{a_1, a_2, a_3\} {a1​,a2​,a3​}，队伍 2： { a 4 , a 5 } \{a_4, a_5\} {a4​,a5​}，力量值和分别为 $10+9+8=27$，$12+14=26$，差距为 $|27-26|=1$。

数据规模与约定

• 对 $20\%$ 的数据，$n\le 50$。
• 对全部的测试数据，保证 $1\le n\le 10^3$，$1\le a_i\le 10^9$。

二分查找 前缀和

preSum记录前缀和。
两层循环，分别枚举l2,r2。
在有序集合s中寻找，最接近preSum[r2+1]-preSum[l2]的数。
在循环l2的结束：
将preSum[l2+1]-perSum[i] 加到s中。i$\in$[0,l2]。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) ;
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	scanf("%d", &n);
	vector<T> ret(n);
	for(int i=0;i < n ;i++) {
		cin >> ret[i];
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

class Solution {
		public:
			long long Ans(vector<int>& a) {
				const int N = a.size();
				vector<long long> preSum(1);
				for (const auto& i : a) { preSum.emplace_back(i + preSum.back()); }
				set<long long> que1;
				long long ans = LLONG_MAX / 2;
				for (int i = 0; i < N; i++) {
					for (int j = i; j < N; j++) {
						auto cur = preSum[j + 1] - preSum[i];
						auto it = que1.lower_bound(cur);
						if (que1.end() != it) {
							ans = min(ans, *it - cur);
						}
						if (que1.begin() != it) {
							--it; ans = min(ans, cur - *it);
						}
					}
					for (int j = 0; j <= i; j++) {
						que1.emplace(preSum[i + 1] - preSum[j]);
					}
				}
				return ans;
			}
		};
int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	auto a = Read<int>();
#ifdef _DEBUG		
	//printf("K=%d", K);
	//Out(b, "b=");
	//Out(a, ",a=");
#endif // DEBUG	
	auto res = Solution().Ans(a);
	cout << res << endl;
	return 0;
}

单元测试

vector<int> a;	
		TEST_METHOD(TestMethod11)
		{
			a = { 10,9,8,12,14 };
			auto res = Solution().Ans(a);
			AssertEx(1LL, res);
		}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。