​欢迎大家订阅我的专栏算法题解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分版本#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long类型constintN1000005;// 定义数组最大长度intt,n,a[N],sa[N],ans;// t: 测试用例数n: 数组长度a: 原始数组sa: 前缀和数组signedmain()// 主函数signed等同于int{cint;// 输入测试用例数量while(t--)// 处理每个测试用例{cinn;// 输入数组长度for(inti1;in;i)// 读取数组元素{cina[i];sa[i]sa[i-1]a[i];// 计算前缀和}intans1e18;// 初始化答案为极大值for(inti1;in;i)// 遍历第一个分割点for(intji1;jn;j)// 遍历第二个分割点{intasa[i];// 第一段的和a[1]到a[i]intbsa[j]-sa[i];// 第二段的和a[i1]到a[j]intcsa[n]-sa[j];// 第三段的和a[j1]到a[n]// 计算最大值与最小值的差并更新答案ansmin(ans,max({a,b,c})-min({a,b,c}));}coutansendl;// 输出当前测试用例的答案}return0;}#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long类型constintN1000005;// 定义数组最大长度intt,n,a[N],sa[N],ans;// t: 测试用例数n: 数组长度a: 原始数组sa: 前缀和数组ans: 最终答案// 计算区间[l, r]的和intcalc(intl,intr){if(lr)// 如果左边界大于右边界return0;// 返回0returnsa[r]-sa[l-1];// 返回前缀和之差}// 检查三个区间的和并更新最小差值voidcheck(inta,intb,intc){ansmin(ans,max({a,b,c})-min({a,b,c}));// 更新最大值与最小值的差的最小值}signedmain()// 主函数signed等同于int{scanf(%d,t);// 输入测试用例数量while(t--)// 处理每个测试用例{cinn;// 输入数组长度for(inti1;in;i)// 读取数组元素{scanf(%d,a[i]);// 输入数组元素sa[i]sa[i-1]a[i];// 计算前缀和}ans1e18;// 初始化答案为极大值for(inti1;in;i)// 遍历分割点i{// 二分查找位置k使得sa[k]最接近sa[i]/2intklower_bound(sa1,san1,sa[i]/2)-sa-1;// 检查两种分割方案check(calc(1,k),calc(k1,i),calc(i1,n));// 方案1在k处分割check(calc(1,k1),calc(k2,i),calc(i1,n));// 方案2在k1处分割}printf(%d\n,ans);// 输出当前测试用例的答案}return0;}【运行结果】2 3 1 10 100 99 8 3 5 1 8 9 2 4 11 6