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$的长度多一倍

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

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

代码

Submission #114775818 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论