題目描述
由比濱結衣做了許多餅干，編號從 1 ～ n，每個餅干有自己的甜度。侍奉部
包括她自己在內一共有三名成員，由比濱結衣想把這些餅干分為甜度接近的三
組，具體分組方法如下：
將這 n 個面包的甜度視作長度為 n 的由正整數組成的序列 a ，將 a 序列
分成連續的三段，即將 a 序列分成 [1, r1], [l2, r2], [l3, n](1 ≤ l1, l1 ≤ r1, r1 + 1 =
l2, l2 ≤ r2, r2 + 1 = l3, l3 ≤ r3, r3 ≤ n) 三個區間。區間和的含義是一個區間內
的所有數的和。現希望能夠使三個區間的區間和之間的極差最小，但是由比濱
結衣的數學不太好，希望你可以寫個程序幫幫她。
輸入
第一行是一個正整數 n，（3 ≤ n ≤ 106)
第二行是 n 個正整數，表示 ai，(1 ≤ ai ≤ 1010)
輸出
輸出一行，一個正整數，表示最終求取到的三個區間的區間和之間的極差。
樣例
樣例輸入 樣例輸出
5
1 4 5 3 8
3
思路：這個題目就比較正常了，很容易想到，分成兩個指針，移動左邊一個，然后將右邊一個指針移動到最優的位置。通過打表發現，每次移動左邊指針到j時，那么右邊指針在哪兒最優呢？就是在[j+1,n]的中間值左右的時候，價值是最優的。這樣我們就可以直接二分找到這個位置，然后在這個位置的左右分別判斷最優值，然后整體取最優的。時間復雜度是O(nlogn).
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e6+100; ll a[maxx]; ll suml[maxx],sumr[maxx]; int n;int main() {scanf("%d",&n);memset(suml,0,sizeof(suml));memset(sumr,0,sizeof(sumr));for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=1;i<=n;i++) suml[i]=suml[i-1]+a[i];for(int i=n;i>=1;i--) sumr[n-i+1]=sumr[n-i]+a[i];ll ans=1e18;for(int i=1;i<=n;i++){ll sum=1e18;ll num=(suml[n]-suml[i])/2ll;//找中間值ll pos=upper_bound(sumr+1,sumr+1+n-i,num)-sumr;ll sum1=suml[i];ll sum2=sumr[pos];ll sum3=suml[n-pos]-suml[i];ll x=max(max(sum1,sum2),sum3);ll y=min(min(sum1,sum2),sum3);if(sum>x-y) sum=x-y;ans=min(ans,sum);pos-=1;sum1=suml[i];sum2=sumr[pos];sum3=suml[n-pos]-suml[i];x=max(max(sum1,sum2),sum3);y=min(min(sum1,sum2),sum3);if(sum>x-y) sum=x-y;ans=min(ans,sum);}printf("%lld\n",ans);return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的2020年第十八届西电程序设计竞赛网络预选赛之Problem D 由比滨结衣的饼干（二分+前缀后缀）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。