題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P3143 [USACO16OPEN] Diamond Collector S

Problem Statement

題目簡述

給定 $N$ 顆鑽石的大小與允許差值 $K$ 。
你可以挑選兩個展示櫃，各自放入一些鑽石；同一個展示櫃內任意兩顆鑽石大小差不可超過 $K$ （差值等於 $K$ 也允許）。
兩個展示櫃使用的鑽石不可重複，求最多能展示的鑽石數量總和。

Constraints

約束條件

$1 \le N \le 50000$
$0 \le K \le 10^9$
每顆鑽石大小為正整數，且 $\le 10^9$

思路：排序後枚舉第二個展示櫃的起點

1. 排序後，單一展示櫃一定是一段連續區間

先把所有鑽石大小排序成遞增序列 $A$ 。

若某個展示櫃最後選到的最小值是 $A[l]$ 、最大值是 $A[r]$ ，且滿足：

A[r] - A[l] \le K

那麼所有夾在中間的鑽石 $A[l+1], A[l+2], \dots, A[r-1]$ `$ 也都同樣合法。既然題目是要最大化展示數量，跳過這些中間元素只會讓答案更差，不可能更好。

因此，排序後每個展示櫃的最優選法都一定對應到一段連續合法區間。

2. 原題等價於選兩段不重疊的合法區間

排序後，原題就變成：

選兩段互不重疊的區間
每段內的最大值與最小值差都不能超過 $K$
最大化兩段長度總和

由於兩段不重疊，所以只要決定第二段從哪裡開始，第一段就必須完全落在它左邊。

3. 枚舉第二段左端點，左邊只維護一個最佳值

定義：

$L[i]$ ：以 $i$ 為右端點時，最小的合法左端點
$R[i]$ ：以 $i$ 為左端點時，最大的合法右端點

那麼：

以 $i$ 為右端點的最長合法區間長度是 $i - L[i] + 1$
以 $i$ 為左端點的最長合法區間長度是 $R[i] - i + 1$

接著從左到右掃描 $i$ ，把它視為第二個展示櫃的左端點：

$c2 = R[i] - i + 1$ ：第二個展示櫃若從 $i$ 開始，最多能放多少顆
$c1$ ：所有右端點 $< i$ 的合法區間中，最大的長度

則目前答案候選值就是：

c1 + c2

更新順序不能反

必須先用舊的 $c1$ 更新答案，再把「以 $i$ 為右端點」的區間納入 $c1$ 。
否則第一段可能也使用第 $i$ 顆鑽石，和第二段重疊。

下面兩種方法的差別，只在於如何求出 $L[i]$ 與 $R[i]$ 。

方法一：二分搜尋預處理左右界

排序後，對每個位置 $i$ 的值 $x = A[i]$ ：

最左合法位置就是第一個滿足 $A[\text{pos}] \ge x - K$ 的位置，因此可以用 $\text{bisect\_left}(A, x - k)$
最右合法位置就是最後一個滿足 $A[\text{pos}] \le x + K$ 的位置，因此可以用 $\text{bisect\_right}(A, x + k) - 1$

如此就能在每個位置各做兩次二分，得到全部的 $L$ 與 $R$ ，再套用前面的掃描流程。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ 。排序是 $\mathcal{O}(n \log n)$ ，每個位置再做兩次二分，仍是 $\mathcal{O}(n \log n)$ 。
空間複雜度： $\mathcal{O}(n)$ 。

方法二：雙指標預處理左右界

其實 $L$ 與 $R$ 都有單調性，所以不一定要每次二分。

先看 $L[j]$ 。當右端點 $j$ 從左往右移動時，合法左端點絕不會往左跑，所以可以維護一個指標 $i$ ：

若 $A[i] < A[j] - K$ ，表示 $i$ 太左了，必須右移
當迴圈結束時， $i$ 就是最小的合法左端點，也就是 $L[j]$

$R[i]$ 也完全對稱。當左端點 $i$ 從右往左移動時，最大的合法右端點只會往左移，因此可以再維護一個從右側出發的指標 $j$ ：

若 $A[j] > A[i] + K$ ，表示 $j$ 太右了，必須左移
當迴圈結束時， $j$ 就是最大的合法右端點，也就是 $R[i]$

這樣預處理 $L$ 、 $R$ 都只要線性時間。雖然整體複雜度仍然被排序主導為 $\mathcal{O}(n \log n)$ ，但區間資訊本身已經是線性求出。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ 。排序佔主導；雙指標預處理與最後掃描皆為 $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(n)$ 。

Code

方法一：二分搜尋預處理左右界

from bisect import bisect_left, bisect_right


def solve():
    n, k = map(int, input().split())
    A = [int(input()) for _ in range(n)]

    A.sort()

    L = [0] * n  # L[i] 表示以 i 為右端點時，最小的合法左端點
    R = [0] * n  # R[i] 表示以 i 為左端點時，最大的合法右端點

    for i, x in enumerate(A):
        L[i] = bisect_left(A, x - k)
        R[i] = bisect_right(A, x + k) - 1

    # 枚舉第二個區間的左端點，根據 R[i] 可以得到第二個區間的最大長度
    # c1 維護所有右端點 < i 的合法區間中，最大的長度
    ans = c1 = 0
    for i in range(n):
        c2 = R[i] - i + 1
        ans = max(ans, c1 + c2)
        c1 = max(c1, i - L[i] + 1)
    print(ans)


if __name__ == "__main__":
    solve()

方法二：雙指標預處理左右界

def solve():
    n, k = map(int, input().split())
    A = [int(input()) for _ in range(n)]

    A.sort()

    L = [0] * n  # L[i] 表示以 i 為右端點時，最小的合法左端點
    R = [0] * n  # R[i] 表示以 i 為左端點時，最大的合法右端點

    i = 0
    for j, x in enumerate(A):
        while i < n and A[i] < x - k:
            i += 1
        L[j] = i

    j = n - 1
    for i in range(n - 1, -1, -1):
        x = A[i]
        while j >= 0 and A[j] > x + k:
            j -= 1
        R[i] = j

    # 枚舉第二個區間的左端點，c1 維護左側最佳合法區間長度
    ans = c1 = 0
    for i in range(n):
        c2 = R[i] - i + 1
        ans = max(ans, c1 + c2)
        c1 = max(c1, i - L[i] + 1)
    print(ans)


if __name__ == "__main__":
    solve()