欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
【题目来源】
合理分工
【题目描述】
一名工人一天可以工作八小时，那么只要一天安排3 33个班次，即3 33名工人依次每人工作八小时，就可以实现工厂一天二十四小时不停工。这就是所谓的"三班倒"。
但对于各项工作任务而言，这些任务往往存在难易差异；在工厂流水线上，这些任务又总是需要按照一定的顺序完成。这时，如何才能合理地安排工作任务，就成为了工厂管理的重要课题。
今天，工厂接到了n nn项工作任务，需要安排3 33名工人轮班，按顺序依次完成每一项任务。其中，第1 11名工人完成前若干项工作，第2 22名工人完成紧接着的若干项工作，第3 33名工人则完成剩下的所有任务。
假设每项任务都有一个固定的困难程度，每名工人的"疲劳程度"为他这一天完成的工作的难度总和。任何工作任务都只能由一名工人独立完成，且任何工人都必须完成至少一项工作任务。
现在，请你帮助工厂合理分配这些任务，使得3 33名工人中，疲劳程度最高的与最低的这两名工人的疲劳程度尽可能地接近，即最小化这两名工人的疲劳程度之差。
【输入】
第一行，包含一个正整数T TT，表示一个测试点所包含的测试数据组数。
接下来2 × T 2×T2×T行，每两行描述一组测试数据：
其中的第一行，包含一个正整数n nn，表示今天的工作任务数。
其中的第二行，包含n nn个由空格分隔的正整数{ a i } \{ a_i \}{ai}，依次表示每项任务的难度。3 33名工人必须按照输入顺序轮班完成这些任务。
【输出】
共T TT行，每行包含一个整数，依次表示在相应测试数据中，疲劳程度最高与最低的两名工人的疲劳程度之差。
【输入样例】
2 3 1 10 100 8 3 5 1 8 9 2 4 11【输出样例】
99 6【算法标签】
#整数二分
【代码详解】
// 40分版本#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long类型constintN=1000005;// 定义数组最大长度intt,n,a[N],sa[N],ans;// t: 测试用例数，n: 数组长度，a: 原始数组，sa: 前缀和数组signedmain()// 主函数，signed等同于int{cin>>t;// 输入测试用例数量while(t--)// 处理每个测试用例{cin>>n;// 输入数组长度for(inti=1;i<=n;i++)// 读取数组元素{cin>>a[i];sa[i]=sa[i-1]+a[i];// 计算前缀和}intans=1e18;// 初始化答案为极大值for(inti=1;i<n;i++)// 遍历第一个分割点for(intj=i+1;j<=n;j++)// 遍历第二个分割点{inta=sa[i];// 第一段的和：a[1]到a[i]intb=sa[j]-sa[i];// 第二段的和：a[i+1]到a[j]intc=sa[n]-sa[j];// 第三段的和：a[j+1]到a[n]// 计算最大值与最小值的差，并更新答案ans=min(ans,max({a,b,c})-min({a,b,c}));}cout<<ans<<endl;// 输出当前测试用例的答案}return0;}#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long类型constintN=1000005;// 定义数组最大长度intt,n,a[N],sa[N],ans;// t: 测试用例数，n: 数组长度，a: 原始数组，sa: 前缀和数组，ans: 最终答案// 计算区间[l, r]的和intcalc(intl,intr){if(l>r)// 如果左边界大于右边界return0;// 返回0returnsa[r]-sa[l-1];// 返回前缀和之差}// 检查三个区间的和，并更新最小差值voidcheck(inta,intb,intc){ans=min(ans,max({a,b,c})-min({a,b,c}));// 更新最大值与最小值的差的最小值}signedmain()// 主函数，signed等同于int{scanf("%d",&t);// 输入测试用例数量while(t--)// 处理每个测试用例{cin>>n;// 输入数组长度for(inti=1;i<=n;i++)// 读取数组元素{scanf("%d",&a[i]);// 输入数组元素sa[i]=sa[i-1]+a[i];// 计算前缀和}ans=1e18;// 初始化答案为极大值for(inti=1;i<=n;i++)// 遍历分割点i{// 二分查找位置k，使得sa[k]最接近sa[i]/2intk=lower_bound(sa+1,sa+n+1,sa[i]/2)-sa-1;// 检查两种分割方案check(calc(1,k),calc(k+1,i),calc(i+1,n));// 方案1：在k处分割check(calc(1,k+1),calc(k+2,i),calc(i+1,n));// 方案2：在k+1处分割}printf("%d\n",ans);// 输出当前测试用例的答案}return0;}【运行结果】
2 3 1 10 100 99 8 3 5 1 8 9 2 4 11 6
