小明是學校里的一名老師,他帶的班級共有 n 名同學,第 i 名同學力量值為 ai。在閑暇之余,小明決定在班級里組織一場拔河比賽。
為了保證比賽的雙方實力盡可能相近,需要在這 n 名同學中挑選出兩個隊伍,隊伍內(nèi)的同學編號連續(xù):{al1, al1+1, ..., ar1?1, ar1} 和 {al2, al2+1, ..., ar2?1, ar2},其中 l1 ≤ r1 < l2 ≤ r2。
兩個隊伍的人數(shù)不必相同,但是需要讓隊伍內(nèi)的同學們的力量值之和盡可能相近。請計算出力量值之和差距最小的挑選隊伍的方式。
輸入共兩行。
第一行為一個正整數(shù) n。
第二行為 n 個正整數(shù) ai。
5 10 9 8 12 14
1
【樣例說明】
其中一種最優(yōu)選擇方式:隊伍 1:{a1, a2, a3},隊伍 2:{a4, a5},力量值和分別為 10 + 9 + 8 = 27,12 + 14 = 26,差距為 |27 ? 26| = 1。
【評測用例規(guī)模與約定】
對于 20% 的評測用例,保證 n ≤ 50。
對于 100% 的評測用例,保證 n ≤ 103,ai ≤ 109。
2024年第十五屆藍橋杯第一次比賽真題,。。。。。。。。。。。。
參加下周比賽的同學可以做一下,體會一下類型和難度