ABC102 D

D - Ecual Cut

問題

整数列A が与えられる．これを4つに区切り，それらを好きな位置でB,C,D,E に分割する．
それぞれについて要素の和をP,Q,R,S とする．P,Q,R,S の最大値と最小値の差の絶対値としてあり得る最も小さい値を求めてください．
問題のリンク　https://abc102.contest.atcoder.jp/tasks/arc100_b

解法

まず累積和を求めておく．
3箇所に区切りを入れるが，まず真ん中の区切りを１つ固定する．
分けた後の整数列をそれぞれ L,R とする．L,R についてさらに区切りを入れる．L,R について区切りを入れる条件は区切りを入れた後の数列の要素の和ができるだけ近いことである．この条件で3つに区切りを入れることができる．
真ん中の区切りが右にずれるに従って L の総和は単調増加，R の総和は単調減少となる．よって L に関して区切りを入れる場合，区切りを左にずらすと絶対値の差が増加してしまうため, それが左にずれることはない．これは Rに関して区切りを入れる場合も同様である．

コード

sample.cpp

#include <iostream>
#include <algorithm>
#include <math.h>

typedef long long ll;
using namespace std;

int main()
{
  int n, i;
  ll a[200001]={0};
  ll p[200001]={0};
  cin >> n;

  for(i=1; i<=n; i++){
    cin >> a[i];
    p[i] = a[i] + p[i-1];
  }

  ll ans = 1e16;
  ll diff[4];

  ll l=1, r=3;

  for(i=2; i<=n; i++){
    while(l<i && abs(p[l]-(p[i]-p[l])) >= abs(p[l+1]-(p[i]-p[l+1]))) l++;
    while(r<n && abs((p[r]-p[i])-(p[n]-p[r])) >= abs((p[r+1]-p[i])-(p[n]-p[r+1]))) r++;

    diff[0]=p[l];
    diff[1]=p[i]-p[l];
    diff[2]=p[r]-p[i];
    diff[3]=p[n]-p[r];

    sort(diff, diff+4);
    ans = min(ans, diff[3]-diff[0]);
  }

  cout << ans << endl;
  return 0;
}