自动搬运

查看原文

来自洛谷，原作者为

	wrh316 Zeit und Raum trennen dich und mich.Informatik verbindet dich und mich. || 一只可爱王法~

搬运于2025-08-24 22:57:59，当前版本为作者最后更新于2024-05-12 21:23:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先对数组 $a$ 从小到大排序，排序后 $a _ {1}$ 一定是极小值，而 $a _ {n}$ 一定是最大值。

如果能找到两个数 $a _ {x}$ 和 $a _ {y}$ 使得 $a _ {x}$ 减去 $a _ {1}$ 和 $a _ {n}$ 减去 $a _ {y}$ 相等并且 $y$ 比 $x$ 要小的话，就一定可以将整个序列分成两半。

我们可以想到：$a _ {x}$ 减去 $a _ {1}$ 和 $a _ {n}$ 减去 $a _ {y}$ 相等就是 $a _ {x}$ 加上 $a _ {y}$ 和 $a _ {1}$ 加上 $a _ {n}$ 相等，所以枚举 $y$，二分查找是否能找到对应的 $x$，就完成了。

上代码：

#include <bits/stdc++.h>
using namespace std;

int t,id,n,ans;
int a[1000005];
bool f;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t>>id;
	while(t--){
		cin>>n;
		for(int i = 1;i <= n;i++) cin>>a[i];
		sort(a + 1,a + n + 1);
		ans = a[1] + a[n];
		f = false;
		for(int i = 2;i <= n - 1;i++){
			bool vis = binary_search(a + i + 1,a + n,ans - a[i]);
			if(vis){
				cout<<"Yes\n";
				f = true;
				break;
			}
		}
		if(!f) cout<<"No\n";
	}
	return 0;
}