🔗 CF2179C Blackslex and Number Theory

rating: 1025

Problem Statement

題意簡述

給定一個陣列 $a_1, a_2, \ldots, a_n$ ，每次操作可以選擇索引 $i$ 和整數 $x \ge k$ ，將 $a_i$ 更新為 $a_i \bmod x$ 。
注意每次操作時可以選擇不同的 $x$ 。
目標是通過有限次操作使數組中所有元素相等。求最大的正整數 $k$ ，使得該目標可能達成。

Constraints

約束條件

$2 \le n \le 2 \cdot 10^5$
$1 \le a_i \le 10^9$ ，且所有 $a_i$ 互不相同

思路：貪心策略與數論分析

這道題的核心在於觀察我們最終能將所有數字變成什麼值。由於操作是取模，數值只會變小或不變。我們主要有兩種貪心策略：

策略 1：將所有數變為 0

我們可以選擇 $x = a_i$ 來將每個 $a_i$ 變為 0。
這要求 $a_i \ge k$ 對所有 $i$ 成立，意味著 $k \le \min(a)$ 。
此策略下，最大的 $k$ 為陣列中的最小值，且此策略總是成立。

策略 2：將所有數變為最小值

\min(a)

我們需要針對每個 $a_i$ 找到滿足 $a_i \bmod x = \min(a)$ 的 $x$ 。根據 $a_i$ 是否為最小值，分為兩種情況討論：

若 $a_i = \min(a)$ ：
無需進行任何操作（或操作次數為 0），此時對 $x$ （以及 $k$ ）沒有限制。
若 $a_i > \min(a)$ ：
必須滿足 $a_i \bmod x = \min(a)$ 且 $x > \min(a)$ 。
這表示 $x$ 必須是 $a_i - \min(a)$ 的因數。
為了讓 $k$ 盡可能大，我們取每個元素能容許的最大 $x$ ，即 $x_i = a_i - \min(a)$ 。
因此，對於所有 $a_i > \min(a)$ ，必須滿足 $k \le a_i - \min(a)$ 。

綜合上述，最嚴格的限制取決於所有 $a_i > \min(a)$ 中 $a_i - \min(a)$ 的最小值。
這發生在 $a_i$ 為陣列中的次小值 ( $a_{second\_min}$ ) 時，即 $k \le a_{second\_min} - \min(a)$ 。

Note

如果 $a_{second\_min} - \min(a) \le \min(a)$ ，此時這個策略計算出的 $k$ 值會在與策略 1 ( $\min(a)$ ) 的比較中被取代，故實作時不用特別檢查 $x > \min(a)$ 這個條件。

結論

綜合上述兩種情況，答案即為 $\max(\min(a), \text{second\_min}(a) - \min(a))$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ 或 $\mathcal{O}(n \log n)$ ，找出最小和次小值即可。
空間複雜度： $\mathcal{O}(n)$ 用於存儲輸入，可優化至 $\mathcal{O}(1)$ 。

Code

from heapq import nsmallest

def solve():
    n = int(input())
    A = list(map(int, input().split()))
    assert len(A) == n

    # 找出陣列中最小的兩個元素
    # nsmallest 可以在 O(n) 時間內找到最小的 k 個元素
    a, b = nsmallest(2, A)
    
    # 策略 1: 目標變為 0，此時 max_k = a
    # 策略 2: 目標變為 a，此時 max_k = b - a (需滿足 b - a > a，否則無效，但會直接被 max 覆蓋)
    print(max(a, b - a))

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

這裡什麼都沒有。