Overview

Given the darkness values \(A_i\) of socks, we want to pair them up such that the absolute difference within each pair is at most \(K\), and find the maximum number of pairs we can make.

Analysis

The pairing condition is “the difference between two socks is at most \(K\)”, and each sock can only be used once. To maximize the number of pairs, we need a “matching strategy that wastes as few socks as possible.”

The key observation is as follows:

• If we sort the socks in ascending order by darkness, similar values end up adjacent to each other.
• After sorting, if we want to pair sock \(A[i]\) with someone, the best candidate is a nearby value (specifically the adjacent \(A[i+1]\)).

Naively “searching for the optimal matching among all combinations” would be infeasible since the number of combinations is enormous (up to \(2\times 10^5\) socks), and this would result in TLE.

Instead, we sort and scan from left to right:

• If the difference between adjacent elements \(A[i]\) and \(A[i+1]\) is at most \(K\), pair these two socks.
• Otherwise, \(A[i]\) cannot be paired with anyone, so discard it and move on.

This greedy approach achieves the maximum.

Why can we discard \(A[i]\) when the difference exceeds \(K\)? - Since the array is sorted, if \(A[i+1]-A[i] > K\), then for any \(j>i+1\), we have \(A[j]\ge A[i+1]\), so \(A[j]-A[i] \ge A[i+1]-A[i] > K\) meaning no subsequent sock can satisfy the condition with \(A[i]\). - Therefore \(A[i]\) will inevitably be left over, so moving forward is optimal.

Also, is it correct to pair adjacent elements when \(A[i+1]-A[i]\le K\)? - If we pair \(A[i]\) with a more distant partner (\(A[i+2]\) or later), the intermediate \(A[i+1]\) is more likely to be left unpaired, potentially reducing the total number of pairs. - Pairing adjacent elements is the most “compact” way to form pairs, which ultimately maximizes the count.

Concrete examples: - \(A=[1,2,10,11]\), \(K=1\) - \((1,2)\) has difference 1, OK → 1 pair - \((10,11)\) also has difference 1, OK → total 2 pairs (maximum)

• \(A=[1,3,4]\), \(K=1\)
  • \((1,3)\) has difference 2, NG → 1 can’t pair with anyone, discard it
  • \((3,4)\) has difference 1, OK → 1 pair (maximum)

Algorithm

1. Sort array \(A\) in ascending order.
2. Start with index \(i=0\) and repeat the following (while \(i+1 < N\)):
   • If \(A[i+1]-A[i] \le K\), pair \((A[i], A[i+1])\), increment the answer by \(+1\), and increase \(i\) by \(2\) (both socks are consumed).
   • Otherwise, \(A[i]\) cannot be paired, so increase \(i\) by \(1\) (discard \(A[i]\)).
3. Output the resulting number of pairs.

This is a simple greedy approach using “sort + single scan (two-pointer style).”

Complexity

• Time complexity: \(O(N\log N)\) (dominated by sorting; the scan is \(O(N)\))
• Space complexity: \(O(N)\) (for storing the array; including sorting overhead, this is sufficient)

Implementation Notes

• Since \(N\) can be up to \(2\times 10^5\), it is safer to read input efficiently using something like sys.stdin.buffer.read().

• After sorting, the difference check simplifies to \(A[i+1]-A[i]\) (no absolute value needed since the array is in ascending order).

• Set the loop condition to while i + 1 < N: to always guarantee that the next element exists.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:]
    A.sort()
    i = 0
    ans = 0
    while i + 1 < N:
        if A[i + 1] - A[i] <= K:
            ans += 1
            i += 2
        else:
            i += 1
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.