테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 두 수의 합 ======

===== 풀이 =====
  * [[ps:problems:boj:2470]]의 응용. 합이 0에 가까운 두 수를 찾는 대신, K에 가까운 두 수를 찾아야 한다.
  * [[ps:problems:boj:2470]]에서 설명한 두가지 방법인 투포인터와 절댓값 기준 정렬을 모두 같은 시간복잡도인 O(nlogn)으로 사용가능하다. 후자의 경우는 정렬 기준을 abs(x)가 아니라 abs(x - K/2)로 잡으면 된다. abs(2*x - K)로 잡으면 나눗셈을 피할수 있어서 좀더 낫다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 9024. 두 수의 합".

- Problem link: https://www.acmicpc.net/problem/9024
- Solution link: http://www.teferi.net/ps/problems/boj/9024

Tags: [Sort]
"""


def main():
    t = int(input())
    for _ in range(t):
        # pylint: disable=unused-variable
        n, K = [int(x) for x in input().split()]
        nums = [int(x) for x in input().split()]

        nums.sort(key=lambda x, k=K: abs(x + x - k))
        sums = [abs(x + y - K) for x, y in zip(nums, nums[1:])]
        print(sums.count(min(sums)))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}