基本情况

AB秒了。

C搞了一个错的二分答案，虽然过样例了。

C. Min-Max Array Transformation

错误分析

没有进一步推导性质，而是觉得数据单调递增估计是二分，然后就无脑写，实际上 check 的正确性没有保证。

bool check(int ind, int now)
{
	if (ind == now) return true;
	if (b[ind] < a[now]) return false;
	if (ind == 1) return true;
	return b[ind - 1] >= a[ind];//并不严谨
}

void solve()
{
	int n; 
	std::cin >> n;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	for (int i = 1; i <= n; i++) std::cin >> b[i];
	for (int i = 1; i <= n; i++)
	{
		int l = 0, r = n, ans = 0;
		while(l <= r)
		{
			int mid = l + (r - l >> 1);
			if (check(mid, i)) r = mid - 1, ans = mid;
			else l = mid + 1;
		}
		if (ans != 0)
			std::cout << b[ans] - a[i] << " ";
		else 
			std::cout << b[i] - a[i] << " ";
	}
	std::cout << std::endl;
	for (int i = 1; i <= n; i++)
	{
		int l = 0, r = n, ans = 0;
		while(l <= r)
		{
			int mid = l + (r - l >> 1);
			if (check(mid, i)) l = mid + 1, ans = mid;
			else r = mid - 1;
		}
		if (ans != 0)
			std::cout << b[ans] - a[i] << " ";
		else 
			std::cout << b[i] - a[i] << " ";
	}
	std::cout << std::endl;
}

正确思路

题意

有两个序列 \(a,b\)。对于每个 \(a_i\)，你需要对 \(b\) 进行重排，使得 \(\forall k,b_k-a_k\ge0\)。问这时 \(b_i-a_i\) 最小、最大分别可能是多少。

多组询问，\(\sum n\le2\times10^5\)。

下面的讨论，记 \(c\) 为重排后的 \(b\)。

\(\texttt{task} _1\)

最小其实很好做。如果没有确定的思考方向，可以发挥 \(\tt CF\) 上非常实用的盲猜法。

对于 \(a_i\) 而言，单纯要让重排后 \(c_i-a_i\) 最小，可以直接让 \(c_i\) 等于b 中大于等于 \(a_i\) 且最小的数，即后继。

这个结论是对的。直接输出后继就完了，接下来我给个证明。

因为题目保证有解，所以最起码对于原来的 \(a,b\) 有 \(\forall k,a_k\le b_k\)。

我们令 \(b_j\) 为 \(b\) 中 \(a_i\) 后继，此时定有 \(b_j\le b_i\)，所以 \(j\le i\)。

然后考虑这样的构造（\(c\) 为重排后的 \(b\)）：

\[c_k=\begin{cases} b_k&k\in[1,j)\\ b_{k+1}&k\in[j,i)\\ b_j&k=i\\ b_k&k\in(i,n] \end{cases}\]

\(\texttt{task} _2\)

有一个关键性质，就是 \(\forall j\le i\)，\(c_j\) 的选择不会影响 \(c_i\) 的选择。原因是根据上面 \(\forall k,b_k\ge a_k\)，\(b_{1\cdots i-1}\) 可以解决 \(a_{1\cdots i-1}\)，不会影响 \(a_i\)。

所以如果你想让单个的 \(c_i-a_i\) 最大，只需要解决 \(i+1\cdots n\) 的影响即可。

然后就是一个贪心的思想。如果 \(c_i\) 尽量的大，那么就要让 \(c_{i+1\cdots n}\) 都尽量的小。

所以我们用一个 set 存下所有的 \(b\)，倒序遍历 \(a\)，然后删除 set 中 \(a_i\) 的后继。删除之前的 set 的最大值就是答案。

\(\texttt{code}\)

void solve()
{
	int n; std::multiset<int> st;
	std::cin >> n;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	for (int i = 1; i <= n; i++) std::cin >> b[i], st.insert(b[i]);
	for (int i = 1; i <= n; i++) 	
		std::cout << *std::lower_bound(b + 1, b + n + 1, a[i]) - a[i] << " ";
	std::cout << std::endl;
	for (int i = n; i >= 1; i--)
	{
		d[i] = *std::prev(st.end(), 1);
		st.erase(st.lower_bound(a[i]));
	}
	for (int i = 1; i <= n; i++)	
		std::cout << d[i] - a[i]<< " ";
	std::cout << std::endl;
}

这里用到了multiset。