【CodeForces–1500A】Going Home

题意#

给定 $n$ 个正整数 $a_1, a_2\cdots, a_n$，求出任意一组 $x\neq y\neq z\neq w$ 使得 $a_x+a_y=a_z+a_w$.

$n\leq 2\times 10^5, 1\leq a_i\leq 2.5\times 10^6$.

分析#

首先考虑暴力，我们开一个 $2a_i\leq 5\times 10^6$ 大小的桶，记录已经找到的和，然后 $\mathcal{O}(n^2)$ 地暴力枚举，直到桶中有元素出现过 $\geq1$ 次，并且满足 $x, y, z, w$ 互不相同即可。

又考虑到这只是 div2. 的 C 题，在这个数据范围上的 $\mathcal{O}(n\log n)$ 做法经过尝试后都行不通。

赛后，我们才知道：非常不幸，这题是结论题。

结论：上面的暴力做法的时间复杂度为：$\mathcal{O}(\min(n^2, n+C))$，$C$ 为 $a_i+a_j$ 的值域。

证明#

首先，如果我们找到了四组两两不完全相同的 $(x_i, y_i)$，使得：

那么就可以找到满足条件的 $x,y, z, w$ 了。

这个结论是非常自然的，简单分类讨论就可以证明。对四个数对中，有多少个 $a_x$ 相同进行讨论：

1. 如果有四个数对的 $a_{x_i}$ 相同，那么 $a_{y_1}=a_{y_2}=a_{y_3}=a_{y_4}$，所以 $y_1, y_2, y_3, y_4$ 是可行的解。
2. 如果有三个数对的 $a_{x_i}$ 相同，不妨设 $a_{x_4}$ 与另外三个数不同，那么 $(x_4, y_4), (x_1, y_1)$ 就是一组可行解。
3. 对于其他情况，显然能找到满足题意的 $x, y, z, w$.

因此，我们只需要用 $\mathcal{O}(n^2)$ 的暴力做法，最差情况是：所输出的答案的 $sum$ 值出现四次。

所有 $sum$ 的可能值只有 $5\times 10^6$ 种，根据抽屉原理，程序复杂度不超过 $2\times 10^7$，可以通过。

代码#

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10, MAXC = 2e6 + 5e5 + 10;
int n;
int x[MAXC << 1], y[MAXC << 1];
int a[MAXN], cnt[MAXC << 1];
bool have_ans;
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			if(cnt[a[i] + a[j]]) {
				if(x[a[i] + a[j]] != i && y[a[i] + a[j]] != i 
                && x[a[i] + a[j]] != j && y[a[i] + a[j]] != j) {
					cout << "YES" << endl << i << " " << j << " " << x[a[i] + a[j]] << " " << y[a[i] + a[j]] << endl;
					return 0;
				}
			} else {
				cnt[a[i] + a[j]]++;
				x[a[i] + a[j]] = i; y[a[i] + a[j]] = j;
			}
		}
	}
	cout << "NO" << endl;
	return 0;
}