[AtCoderARC100D] Equal Cut (枚举, 二分)

发表于 | 分类于 ， | 评论数： | 阅读次数：

链接：https://arc100.contest.atcoder.jp/tasks/arc100_b

给你n个数，要求你不改变顺序将这n个数字切分成4段，问四段中各段求和后最大和与最小和之间的差

切三刀，可以首先枚举中间拿刀，然后再在两边分别二分各自的那一刀，让各自拆分成的两个集合的和的差值最小，这样才能保证整体的差值最小。这题对我来说挺难写的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
int n;
vector<LL> a, s;

LL gao(int id) {
  LL ret = 1E18, tmp = 1E18;
  int lo = 1, hi = id, s1 = 1, s2 = 1;
  while(lo <= hi) {
    int mid = (lo + hi) >> 1;
    if(tmp == 1E18 || tmp > (LL)abs(s[id]-s[mid]-s[mid])) {
      tmp = (LL)abs(s[id]-s[mid]-s[mid]);
      s1 = mid;
    }
    if(s[id]-s[mid]<s[mid]) hi = mid - 1;
    else lo = mid + 1;
  }
  lo = id + 1, hi = n, tmp = 1E18;
  while(lo <= hi) {
    int mid = (lo + hi) >> 1;
    if(tmp == 1E18 || tmp > (LL)abs(s[n]-s[mid]-(s[mid]-s[id]))) {
      tmp = (LL)abs(s[n]-s[mid]-(s[mid]-s[id]));
      s2 = mid;
    }
    if(s[n]-s[mid]<s[mid]-s[id]) hi = mid - 1;
    else lo = mid + 1;
  }
  LL L = min({s[s1], s[id]-s[s1], s[s2]-s[id], s[n]-s[s2]});
  LL R = max({s[s1], s[id]-s[s1], s[s2]-s[id], s[n]-s[s2]});
  ret = min(ret, R-L);
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  while(cin >> n) {
    a.resize(n+1); s.resize(n+1);
    for(int i = 1; i <= n; i++) {
      cin >> a[i];
      s[i] = s[i-1] + a[i];
    }
    LL ret = 1E18;
    for(int i = 1; i <= n; i++) {
      ret = min(ret, gao(i));
    }
    cout << ret << endl;
  }
  return 0;
}

https://arc100.contest.atcoder.jp/tasks/arc100_b