AT_abc318_f [ABC318F] Octopus

· · 题解

首先考虑如何判断当头部位于 k_0 时是否可以抓住所有 n 个宝物。

显然可以排序后贪心将触手与宝藏配对。

然后考虑怎样的 k_0 作为分界点，即头部位于 k_0 满足条件而头部位于 k_0+1 不满足条件和头部位于 k_0 不满足条件而头部位于 k_0+1 满足条件的所有 k_0。

在这种情况下，一定有这样的 i,j 满足 k_0-L_j\le x_i \le k_0+L_j 且 k_0+1-L_j >x_i 或 k_0+1+L_j < x_i。

解不等式得 k_0=x_i+L_j。

在这种情况下，一定有这样的 i,j 满足 k_0+1-L_j\le x_i \le k_0+1+L_j 且 k_0-L_j >x_i 或 k_0+L_j < x_i。

解不等式得 k_0=x_i-L_j-1。

至此，我们找出了所有分界点，所以相邻分界点内的点一定相同，即将所有分界点按升序排序后放入 S 后，当 k_0=S_i 满足条件时，所有 S_{i-1}+1\le k_0 \le S_i 的 k_0 均满足条件。

时间复杂度 \mathcal O(N^3 \log n)。

const int N = 205;
#define int ll
int n, x[N], l[N], s[N * N << 1], ans;
bool chk(int k)
{
    priority_queue <int> q;
    R(i, 1, n) q.push(abs(x[i] - k));
    R(i, 1, n)
    {
        if (q.top() > l[i]) return false;
        q.pop();
    }
    return true;
}
signed main() 
{
    cin >> n;
    R(i, 1, n) cin >> x[i];
    R(i, 1, n) cin >> l[i];
    sort(l + 1, l + n + 1, greater <int> ());
    int tot = 0;
    R(i, 1, n)
    {
        R(j, 1, n)
        {
            s[++tot] = x[i] - l[j] - 1;
            s[++tot] = x[i] + l[j];
        }
    }
    sort(s + 1, s + tot + 1);
    R(i, 2, tot) 
    {
        if (chk(s[i])) ans += s[i] - s[i - 1];
    }
    cout << ans << endl;
    return 0;
}