题解 CF1840D Wooden Toy Festival

Problem

给定 $n$ 个数 $a_1, a_2, a_3, \cdots, a_n$，自选 $3$ 个数 $x, y, z$ 使

$$\max\limits_{i = 1}^{n} \{\min\{|a_i - x|, |a_i - y|, |a_i - z|\}\}$$

最小。求这个最小值。

Solution

考虑将 $a$ 分为 $3$ 个区间，使区间中最大数与最小数之差不超过 $m$，利用二分法求 $m$ 的最小值，可以确定唯一的分割方法。

$x, y, z$ 分别取 $3$ 个区间中最大值与最小值的平均数。最后直接算出结果即可。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
#define elif else if
#define il inline

int t, n;
int a[200005];

int nxt(int x)
{
    int l = 0, r = n + 1;
    while (r - l > 1)
    {
        int m = (l + r) / 2;
        if (a[m] < x)
            l = m;
        else
            r = m;
    }
    return a[r];
}
int pre(int x)
{
    int l = 0, r = n + 1;
    while (r - l > 1)
    {
        int m = (l + r) / 2;
        if (a[m] < x)
            l = m;
        else
            r = m;
    }
    return a[l];
}

bool chk(int d)
{
    int i = 1;
    for (int c = 1; c <= 3; c++)
        i = nxt(nxt(i) + d);
    return i > a[n];
}
vector<vector<int> > get(int d)
{
    vector<vector<int> > vv(3, vector<int>()); 
    int i = 1, j = 1;
    for (int c = 1; c <= 3; c++)
    {
        i = nxt(nxt(i) + d);
        for (; a[j] < i && j <= n; j++)
            vv[c - 1].push_back(a[j]);
    }
    return vv;
}

int sum(vector<int> &v, int c)
{
    int ans = 0;
    for (auto i : v)
        ans = max(ans, abs(c - i));
    return ans;
}
int cal(vector<int> &v)
{
    if (v.size() <= 1)
        return 0;
    return sum(v, (v[0] + v[v.size() - 1]) / 2);
}

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        a[0] = a[n + 1] = inf;
        sort(a + 1, a + n + 1);
        int l = 0, r = 1e9;
        while (r - l > 1)
        {
            int m = (l + r) / 2;
            if (chk(m))
                r = m;
            else
                l = m;
        }
        vector<vector<int> > vv = get(r);
        int ans = 0;
        for (auto i : vv)
        {
//            if (!i.empty())
//            {
//                cout << "  ";
//                for (auto j : i)
//                    cout << j << " ";
//                cout << endl;
//                cout << "  " << (i[0] + i[i.size() - 1]) / 2 << " " << cal(i) << endl;
//            }
            ans = max(ans, cal(i));
        }
        cout << ans << endl;
    }
    return 0;
}

---

• 分类： OI 题解
• 标签： 无标签