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

本文涉及的根本知识点

本博文代码打包下载
C++二分查找
C++算法&#xff1
a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包罗课程视频
[蓝桥杯 2024 省 B] 拔河

标题形貌

小明是学校里的一名老师，他带的班级共有                               n                          n               n 名同砚，第                               i                          i               i 名同砚力气值为                                        a                         i                                  a_i               ai​。在闲暇之余，小明决定在班级里构造一场拔河比赛。
为了包管比赛的两边力气尽大概相近，必要在这                               n                          n               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
                              ≤                               r                         1
                              <                               l                         2                              ≤                               r                         2                                  l_1
\le r_1
<l_2 \le r_2               l1
​≤r1
​<l2​≤r2​。
两个队伍的人数不必类似，但是必要让队伍内的同砚们的力气值之和尽大概相近。请盘算着力气值之和差距最小的挑选队伍的方式。
输入格式

输入共两行。
第一举动一个正整数                               n                          n               n。
第二举动                               n                          n               n 个正整数                                        a                         1
                              ,                               a                         2                              ,                      …                               a                         n                                  a_1
, a_2, \dots a_n               a1
​,a2​,…an​。
输特别式

输出共一行，一个非负整数，体现两个队伍力气值之和的最小差距。
样例 #1


样例输入 #1

1. 5
2. 1
3. 0 9 8 1
4. 2 1
5. 4

复制代码

样例输出 #1

1. 1

复制代码

提示

样例 1
表明

此中一种最优选择方式&#xff1
a;
队伍 1
&#xff1
a;                              {                               a                         1
                              ,                               a                         2                              ,                               a                         3                              }                          \{a_1
, a_2, a_3\}               {a1
​,a2​,a3​}，队伍 2&#xff1
a;                              {                               a                         4                              ,                               a                         5                              }                          \{a_4, a_5\}               {a4​,a5​}，力气值和分别为                               1
0                      +                      9                      +                      8                      &#61
;                      27                          1
0 + 9 + 8 &#61
; 27               1
0+9+8&#61
;27，                              1
2                      +                      1
4                      &#61
;                      26                          1
2 + 1
4 &#61
; 26               1
2+1
4&#61
;26，差距为                               ∣                      27                      −                      26                      ∣                      &#61
;                      1
                          |27 − 26| &#61
; 1
               ∣27−26∣&#61
;1
。
数据规模与约定

• 对                                    20                         %                              20\%                  20% 的数据，                                   n                         ≤                         50                              n \leq 50                  n≤50。
  
• 对全部的测试数据，包管                                    1
                           ≤                         n                         ≤                         1
                                     0                            3                                       1
  \leq n \leq 1
  0^3                  1
  ≤n≤1
  03，                                   1
                           ≤                                   a                            i                                  ≤                         1
                                     0                            9                                       1
  \leq a_i \leq 1
  0^9                  1
  ≤ai​≤1
  09。
  

二分查找 前缀和

preSum记载前缀和。
两层循环，分别罗列l2,r2。
在有序聚集s中探求，最靠近preSum[r2+1
]-preSum[l2]的数。
在循环l2的竣事&#xff1
a;
将preSum[l2+1
]-perSum 加到s中。i                              ∈                          \in               ∈[0,l2]。
代码

核心代码

1. #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
2. , class T2>std::istream& operator >> (std::istream& in, pair<T1
3. , T2>& pr) {        in >> pr.first >> pr.second;        return in;}template<class T1
4. , class T2, class T3 >std::istream& operator >> (std::istream& in, tuple<T1
5. , T2, T3>& t) {        in >> get<0>(t) >> get<1
6. >(t) >> get<2>(t) ;        return in;}template<class T1
7. , class T2, class T3, class T4 >std::istream& operator >> (std::istream& in, tuple<T1
8. , T2, T3, T4>& t) {        in >> get<0>(t) >> get<1
9. >(t) >> get<2>(t) >> get<3>(t);        return in;}template<class T &#61
10. ; int>vector<T> Read() {        int n;        scanf("%d", &n);        vector<T> ret(n);        for(int i&#61
11. ;0;i < n ;i++) {                cin >> ret[i];        }        return ret;}template<class T &#61
12. ; int>vector<T> Read(int n) {        vector<T> ret(n);        for (int i &#61
13. ; 0; i < n; i++) {                cin >> ret[i];        }        return ret;}class Solution {                public:                        long long Ans(vector<int>& a) {                                const int N &#61
14. ; a.size();                                vector<long long> preSum(1
15. );                                for (const auto& i : a) { preSum.emplace_back(i + preSum.back()); }                                set<long long> que1
16. ;                                long long ans &#61
17. ; LLONG_MAX / 2;                                for (int i &#61
18. ; 0; i < N; i++) {                                        for (int j &#61
19. ; i; j < N; j++) {                                                auto cur &#61
20. ; preSum[j + 1
21. ] - preSum[i];                                                auto it &#61
22. ; que1
23. .lower_bound(cur);                                                if (que1
24. .end() !&#61
25. ; it) {                                                        ans &#61
26. ; min(ans, *it - cur);                                                }                                                if (que1
27. .begin() !&#61
28. ; it) {                                                        --it; ans &#61
29. ; min(ans, cur - *it);                                                }                                        }                                        for (int j &#61
30. ; 0; j <&#61
31. ; i; j++) {                                                que1
32. .emplace(preSum[i + 1
33. ] - preSum[j]);                                        }                                }                                return ans;                        }                };int main() {#ifdef _DEBUG        freopen("a.in", "r", stdin);#endif // DEBUG                auto a &#61
34. ; Read<int>();#ifdef _DEBUG                        //printf("K&#61
35. ;%d", K);        //Out(b, "b&#61
36. ;");        //Out(a, ",a&#61
37. ;");#endif // DEBUG                auto res &#61
38. ; Solution().Ans(a);        cout << res << endl;        return 0;}

复制代码

单元测试

1. vector<int> a;                        TEST_METHOD(TestMethod1
2. 1
3. )                {                        a &#61
4. ; { 1
5. 0,9,8,1
6. 2,1
7. 4 };                        auto res &#61
8. ; Solution().Ans(a);                        AssertEx(1
9. LL, res);                }

复制代码

扩展阅读

我想对各人说的话工作中遇到的题目，可以按种别查阅鄙人的算法文章，请点击《算法与数据汇总》。学习算法&#xff1
a;按章节学习《喜缺全书算法册》，大量的标题和测试用例，打包下载。器重操纵有效学习&#xff1
a;明确的目的 及时的反馈 拉伸区（难度符合） 专注闻缺陷则喜(喜缺)是一个优美的愿望，早发现题目，早修改题目，给老板节省钱。子墨子言之&#xff1
a;事无终始，无务多业。也就是我们常说的专业的人做专业的事。假如步伐是一条龙，那算法就是他的是睛失败+反思&#61
;乐成 乐成+反思&#61
;乐成视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的解说。
https://edu.csdn.net/course/detail/38771

怎样你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/61
76
测试情况

操纵体系&#xff1
a;win7 开辟情况&#xff1
a; VS201
9 C++1
7
大概 操纵体系&#xff1
a;win1
0 开辟情况&#xff1
a; VS2022 C++1
7
如无特殊分析，本算法用**C++**实现。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。