Wooden Toy Festival 题解：二分答案与贪心验证

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int mod = 1e6+10;
5
typedef long long ll;
6
#define x first
7
#define y second
8
typedef pair<int, int> P;
9

10
ll v[mod];
11
ll n;
12

13
bool check(ll x) {
14
  int cur = 0;
15
    for (int i = 0; i < 3; ++i) {
16
        int start = v[cur];
17
        int end = start + 2 * x;
18
        while (cur < n && v[cur] <= end) {
19
            ++cur;
20
        }
21
        if (cur >= n) {
22
            return true;
23
        }
24
    }
25

26
    return cur >= n;
27
}
28

29
void solve() {
30
  cin >> n;
31

32
  for (int i = 0; i < n; i++) {
33
    cin >> v[i];
34
  }
35

36
  sort(v, v+n);
37

38
  ll l = 0, r = 1e9;
39
  ll mid,ans=1e9;
40
  //mid为三者雕刻所需要的最大时间
41
  //check的时候，尽可能多的在mid时间内为雕刻师安排多的v
42
  //显然这个问题具有单调性，如果用时越久，模具的制作偏差就越大
43
  while (l <= r) {
44
    mid=(l+r)>>1;
45
    if (check(mid)) {
46
      r = mid-1;
47
      ans = mid;
48
    } else {
49
      l = mid+1;
50
    }
51
  }
52
  cout << ans << endl;
53
}
54

55
int main() {
56
    ios_base::sync_with_stdio(false);
57
    cin.tie(NULL);
58
    cout.tie(NULL);
59

60
  int t;
61
  cin >> t;
62
  while(t--) solve();
63

64
  return 0;
65
}