环形分厂协调补货拼多多技术岗 8月2号笔试 第四题题目内容某公司在nnn个城市设有区域分仓分仓沿一条环形物流干线布局——仓111与仓222相邻仓222与仓333相邻……仓nnn与仓111相邻首尾相接构成一个环。每个分仓iii需要补充aia_iai件货物aia_iai为非负整数。总部通过“补货班次”完成补货每个班次中调度员选择一组分仓进行集中补货被选中的分仓各补111件货物。由于环形干线上同一班次内相邻两个分仓同时补货会共用同一传送带从而产生调度冲突因此每个班次选中的分仓集合必须是环上的独立集——即任何两个被选中的分仓在环上都不能相邻注意仓111与仓nnn也是相邻的。每个班次耗时111小时。每个分仓iii必须恰好被补货aia_iai次。请你计算最少需要多少个班次才能完成全部补货任务。输入描述第一行一个正整数TTT表示测试数据组数。对于每组测试数据第一行一个正整数nnn(1≤n≤2×105)(1 \le n \le 2 \times 10^5)(1≤n≤2×105)表示分仓数量。第二行nnn个非负整数a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an(0≤ai≤109)(0 \le a_i \le 10^9)(0≤ai≤109)其中aia_iai表示分仓iii需要补货的件数。输出描述对于每组测试数据输出一行一个整数表示最少需要的班次数。补充说明保证所有测试数据的nnn之和不超过2×1062 \times 10^62×106。样例1输入1 3 1 1 1输出3说明(n3)(n3)(n3)三个仓两两相邻仓111与仓222、仓222与仓333、仓333与仓111都相邻因此任意一个班次里至多只能选中111个分仓补货。三个仓各需补111件无法合并到同一班次故至少需要333个班次。一种可行方案是班次111补仓111班次222补仓222班次333补仓333。样例2输入1 4 3 0 3 0输出3说明(n4)(n4)(n4)仓111与仓333不相邻、仓222与仓444不相邻所以一个班次可以同时选中{1,3}\{1,3\}{1,3}或{2,4}\{2,4\}{2,4}。仓111、仓333各需333件仓222、仓444不需补货。每次都选{1,3}\{1,3\}{1,3}同时补111件重复333个班次即可完成全部补货又因仓111单独就需要333次不可能少于333个班次故答案为333。样例3输入1 6 1 2 3 1 2 3输出5说明(n6)(n6)(n6)环上相邻关系为111-222-333-444-555-666-111。仓222与仓333相邻二者不能在同一班次被同时补货因此它们合计需要的(235)(235)(235)次补货必须分散在555个互不相同的班次中所以班次不可能少于555。另一方面确实可以用555个班次完成全部补货例如班次111选{2,5}\{2,5\}{2,5}班次222选{3,6}\{3,6\}{3,6}班次333选{3,6}\{3,6\}{3,6}班次444选{1,3,5}\{1,3,5\}{1,3,5}班次555选{2,4,6}\{2,4,6\}{2,4,6}每个班次内的仓在环上两两不相邻符合独立集要求。累计仓111补111次、仓222补222次、仓333补333次、仓444补111次、仓555补222次、仓666补333次恰好满足需求。故答案为555。题解思路数学原理这类题对于环形图有个公式当n 1是答案就是a[0]当n为偶数时答案为max(ai ai1)当n为奇数时答案为max(max(ai ai1), sum(a)/(n 2))因此可以使用O(n)解决这个问题。C#includebits/stdc.husingnamespacestd;usinglllonglong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn;cinn;vectorlla(n);for(inti0;in;i){cina[i];}// 只有一个仓库的if(n1){couta[0]endl;continue;}ll sum0;ll maxAdjacent0;// 计算总和 以及 相邻仓库最大和for(inti0;in;i){suma[i];maxAdjacentmax(maxAdjacent,a[i]a[(i1)%n]);}ll ansmaxAdjacent;// 奇数环还需要考虑每个班次最多能补多少个仓库if(n%2){ll maxBatchn/2;ll needBySum(summaxBatch-1)/maxBatch;ansmax(ans,needBySum);}coutansendl;}}javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intTInteger.parseInt(br.readLine().trim());while(T--0){intnInteger.parseInt(br.readLine().trim());long[]anewlong[n];String[]numsbr.readLine().trim().split( );for(inti0;in;i){a[i]Long.parseLong(nums[i]);}// 只有一个仓库的if(n1){System.out.println(a[0]);continue;}longsum0;longmaxAdjacent0;// 计算总和 以及 相邻仓库最大和for(inti0;in;i){suma[i];maxAdjacentMath.max(maxAdjacent,a[i]a[(i1)%n]);}longansmaxAdjacent;// 奇数环还需要考虑每个班次最多能补多少个仓库if(n%21){longmaxBatchn/2;longneedBySum(summaxBatch-1)/maxBatch;ansMath.max(ans,needBySum);}System.out.println(ans);}}}pythonTint(input())whileT0:T-1nint(input())alist(map(int,input().split()))# 只有一个仓库的ifn1:print(a[0])continuesum_val0maxAdjacent0# 计算总和 以及 相邻仓库最大和foriinrange(n):sum_vala[i]maxAdjacentmax(maxAdjacent,a[i]a[(i1)%n])ansmaxAdjacent# 奇数环还需要考虑每个班次最多能补多少个仓库ifn%21:maxBatchn//2needBySum(sum_valmaxBatch-1)//maxBatch ansmax(ans,needBySum)print(ans)javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,line{input.push(line.trim());});rl.on(close,(){letindex0;letTNumber(input[index]);while(T--0){letnNumber(input[index]);letainput[index].split( ).map(Number);// 只有一个仓库的if(n1){console.log(a[0]);continue;}letsum0;letmaxAdjacent0;// 计算总和 以及 相邻仓库最大和for(leti0;in;i){suma[i];maxAdjacentMath.max(maxAdjacent,a[i]a[(i1)%n]);}letansmaxAdjacent;// 奇数环还需要考虑每个班次最多能补多少个仓库if(n%21){letmaxBatchMath.floor(n/2);letneedBySumMath.floor((summaxBatch-1)/maxBatch);ansMath.max(ans,needBySum);}console.log(ans);}});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()varTintfmt.Fscan(in,T)forT0{T--varnintfmt.Fscan(in,n)a:make([]int64,n)fori:0;in;i{fmt.Fscan(in,a[i])}// 只有一个仓库的ifn1{fmt.Fprintln(out,a[0])continue}varsumint64varmaxAdjacentint64// 计算总和 以及 相邻仓库最大和fori:0;in;i{suma[i]current:a[i]a[(i1)%n]ifcurrentmaxAdjacent{maxAdjacentcurrent}}ans:maxAdjacent// 奇数环还需要考虑每个班次最多能补多少个仓库ifn%21{maxBatch:int64(n/2)needBySum:(summaxBatch-1)/maxBatchifneedBySumans{ansneedBySum}}fmt.Fprintln(out,ans)}}