抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

考虑构造出一种方法,使得尽可能不存在题目中 $a_i+a_j=T$ 的二元组 $(i,j)$。

令 $res\gets\dfrac{T}{2}$,可以发现元素的大小都是非负数,因此若 $a_i+a_j=T$ 成立,有两种情况:

  1. $a_i=a_j=res$;

  2. 若 $a_ires$。

因此我们可以把所有小于 $res$ 的分成一组,大于 $res$ 的分成一组;等于 $res$ 的只需要保证每组个数相同或差 $1$,即换着分即可。

时间复杂度 $\mathcal O(t\cdot n)$。

发言区

留下自己的足迹吧~