Codeforces Round 878 (Div. 3) - D. Wooden Toy Festival

Solost

2023 年 07 月 07 日

182 次浏览

暂无评论

1498字数

题目题解

# 题目链接

[链接](https://codeforces.com/contest/1840/problem/D)

## 题目大意

给一个长度为n的数组，问你有三个数，x,y,z,使得min(ans, max(abs(x - ai), abs(y - ai), abs(z - ai))的值是多少？

## 题解

这就相当于一个排完序的数组，然后分成三段，这三段分别是最集中的，然后分别求着三段的半径。最暴力的办法就是直接寻找两个中断点，但是这个时间复杂度是O(N * N) ,无法通过，那么我们可以发现，固定第一段的端点，就相当于把后一段分成两段，让这两段的最大值最小，那么办法就是二分，随着端点向右移动，左边区间的贡献值不断增大，右边的不断减小，那么他俩最相近的时候就是贡献值最小的时候。然后第一个端点的遍历时间复杂度是n，二分是logn，在这个数量级下是可以通过的。然后把这个数组分成三段，问题就转换成这三段的半径最长的最短是多少？

## 代码

```cpp
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int a[N], n;

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (n <= 3) {
        cout << "0\n";
        return;
    }
    sort(a + 1, a + n + 1);
    int ans = INT_MAX;
    for (int i = 1; i <= n - 2; i++) {
        if ((a[i] - a[1] + 1) / 2 >= ans)//如果目前的答案比现有的还大，没必要往下搜
            continue;
        int l = i + 1, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            ans = min(ans, (max(max(a[i] - a[1], a[mid] - a[i + 1]), a[n] - a[mid + 1]) + 1) / 2);
            if ((a[mid] - a[i + 1] + 1) / 2 < (a[n] - a[mid + 1] + 1) / 2)//这个位置>=和>是没有影响的，因为我们都会向上取整
                l = mid + 1;
            else
                r = mid;
        }
    }
    cout << ans << endl;
}
int main()
{
    IOS;
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 07 月 07 日