打卡信奥刷题（3449）用C++实现信奥题 P10429 [蓝桥杯 2024 省 B] 拔河

P10429 [蓝桥杯 2024 省 B] 拔河题目描述小明是学校里的一名老师他带的班级共有nnn名同学第iii名同学力量值为aia_iai​。在闲暇之余小明决定在班级里组织一场拔河比赛。为了保证比赛的双方实力尽可能相近需要在这nnn名同学中挑选出两个队伍队伍内的同学编号连续{al1,al11,…,ar1−1,ar1}\{{a_{l_1}}, a_{l_1 1}, \dots, a_{r_1 - 1}, a_{r_1}\}{al1​​,al1​1​,…,ar1​−1​,ar1​​}和{al2,al21,…,ar2−1,ar2}\{{a_{l_2}}, a_{l_2 1}, \dots, a_{r_2 - 1}, a_{r_2}\}{al2​​,al2​1​,…,ar2​−1​,ar2​​}其中l1≤r1l2≤r2l_1 \le r_1l_2 \le r_2l1​≤r1​l2​≤r2​。两个队伍的人数不必相同但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。输入格式输入共两行。第一行为一个正整数nnn。第二行为nnn个正整数a1,a2,…,ana_1, a_2, \dots ,a_na1​,a2​,…,an​。输出格式输出共一行一个非负整数表示两个队伍力量值之和的最小差距。输入输出样例 #1输入 #15 10 9 8 12 14输出 #11说明/提示样例 1 解释其中一种最优选择方式队伍111{a1,a2,a3}\{a_1, a_2, a_3\}{a1​,a2​,a3​}队伍222{a4,a5}\{a_4, a_5\}{a4​,a5​}力量值和分别为10982710 9 8 2710982712142612 14 26121426差距为∣27−26∣1|27 − 26| 1∣27−26∣1。数据规模与约定对20%20\%20%的数据n≤50n \leq 50n≤50。对全部的测试数据保证2≤n≤1032 \leq n \leq 10^32≤n≤1031≤ai≤1091 \leq a_i \leq 10^91≤ai​≤109。C实现#includebits/stdc.husingnamespacestd;constintmaxn1e310;intn;longlonga[maxn],ans1e9;multisetlonglongS;longlongminnum(longlonga,longlongb){returnab?b:a;}intmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinn;for(inti1;in;i)cina[i],a[i]a[i-1]a[i];//前缀和维护for(inti1;in;i)for(intji;jn;j)S.insert(a[j]-a[i-1]);//全部插入for(inti1;in;i){for(intji;jn;j){autopS.find(a[j]-a[i-1]);S.erase(p);//删除}for(intj1;ji;j){autoka[i]-a[j-1];autopS.lower_bound(k);if(p!S.end())ansminnum(ans,abs(*p-k));if(p!S.begin())p--,ansminnum(ans,abs(*p-k));}}coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容