Codeforces Round #707 Going Home - 复杂度分析

题意

给你一个长度为$n$的数组$a$，问你能不能从中找出4个数使得$a_x + a_y = a_z + a_w$。

题解

首先，可以想到$a_x + a_y = a_z + a_w$可以转化为$a_x - a_w = a_z - a_y$。于是整个问题就变成了找到差相等的配对。

那么最多有多少种差呢？其实最多只有2500种差可能。考虑所有可能的差是$(0,1,2,3,4,...)$，那么$a$从小到大的值应该是$(1,1,2,4,7,11,...)$。我们可以发现，差为2500时，就已经超过了$a$的最大值。

同时我们需要注意到，每个数只能用一次。因此$n\geq 5000$时，必有解。

于是，对于$n\geq 5000$的情况，对于排序后的$a$，相邻两个数的差至少有一个会出现多于3次。

对于$n<5000$。我们直接$n^2$暴力找出任意两个数的差即可。

代码