AT_abc318_f [ABC318F] Octopus

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

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

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

• 头部位于 \(k_0\) 满足条件而头部位于 \(k_0+1\) 不满足条件

在这种情况下，一定有这样的 \(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\)。

• 头部位于 \(k_0\) 不满足条件而头部位于 \(k_0+1\) 满足条件

在这种情况下，一定有这样的 \(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;
}