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

🔗 CF2183C War Strategy

rating: 1454

Problem Statement

題目簡述

在一直線上， $n$ 個基地位於 $1 \dots n$ ，第 $k$ 個為大本營。
每天可使某個基地上的任意數量士兵向左或右移動一格（全體同向），隨後大本營生成一新兵。
求 $m$ 天後最多能有多少個基地被士兵佔據。

Constraints

約束條件

$1 \le k \le n \le 10^5$
$1 \le m \le 10^9$

思路：枚舉(Enumeration) + 貪心(Greedy)

枚舉左側延伸的長度 $x$ ，計算達成該長度所需的最小天數以及剩餘的士兵資源，然後利用剩餘的天數和資源去計算右側最大可以延伸的長度 $y$ 。由於在移動後大本營會生成一新兵，因此大本營總是可以被占據的，最終答案為 $\max(x + y + 1)$ 。

如何佔據左側 $x$ 格（右側同理）

假設大本營目前有 $v$ 個士兵，目標是佔據左側的 $x$ 個格子（即 $k-1, k-2, \dots, k-x$ ）。

構造最優操作方案

階段一：用 $v$ 個士兵佔據最左邊的 $v$ 格

將 $v$ $v$ 個士兵向左移動 $x$ $x$ 步，但最後 $v-1$ 步逐一留人：
- 第 $1$ ～第 $x-v+1$ 步： $v$ 人全體向左（從 $k$ 推進到 $k-(x-v+1)$ ）
- 第 $x-v+2$ 步： $v-1$ 人繼續移動到 $k-(x-v+2)$ ，留 1 人在 $k-(x-v+1)$
- 第 $x-v+3$ 步： $v-2$ 人繼續移動到 $k-(x-v+3)$ ，留 1 人在 $k-(x-v+2)$
- …
- 第 $x$ 步：1 人移動到 $k-x$ ，留 1 人在 $k-x+1$
這 $x$ 步佔據了最左邊的 $v$ 格（ $k-x, k-x+1, \dots, k-x+v-1$ ），同時大本營累積了 $x$ 個新士兵。

階段二：用新士兵填補剩餘的 $x-v$ 格

剩餘的 $x-v$ 個格子（ $k-x+v, \dots, k-1$ ）只需再執行 $x-v$ 次操作即可填滿。
總消耗： $x + (x-v) = 2x - v$ 天，且最後大本營剩下 $v + x + (x - v) - x = x$ 個士兵。

正確性證明

必要時間 $x$ ：要佔據距離為 $x$ 的 $k-x$ ，士兵至少需要移動 $x$ 步，故前 $x$ 天是必須的。
資源最大化利用：在推進到 $k-x$ 的過程中，我們擁有初始的 $v$ 個士兵。為了效益最大化，這 $v$ 個士兵應被安置在距離最遠（最難到達） 的 $v$ 個位置上（即 $k-x$ 到 $k-x+v-1$ ）。
填補近處缺口：剩餘未被佔據的是距離較近的 $x-v$ 個位置（ $k-1$ 到 $k-x+v$ ）。由於在第一階段的 $x$ 天內，大本營已新生成 $x$ 個士兵（足夠覆蓋缺口），我們只需再花 $x-v$ 天（第一天推 $x-v$ 人到 $k-1$ ，第二天推 $x-v-1$ 人到 $k-2$ …）即可填滿這些近處空缺。
結論：若不將初始士兵用於最遠端，則留下的缺口會更遠，導致第二階段填補耗時增加。故 $2x-v$ 為最優解。

另一種構造方案

另一種構造方式是先在原地累積到 $x$ 個士兵，再向左推進 $x$ 步。
累積 $x$ 個士兵需要 $x - v$ 天，再向左推進 $x$ 步需要 $x$ 天，總共也是 $2x - v$ 天。

注意

上述構造方案僅適用於 $x \ge v$ 的情況，若 $x < v$ 則顯然是錯誤的。
當 $x < v$ 時，直接移動 $x$ 步即可。
由於初始值 $v = 1$ ，在考慮左側時，我們需要特別處理 $x=0$ 的情況。

結論

此時向左延伸 $x$ 格的策略如下：

士兵數量溢出：若 $x < v$ ，則有足夠的士兵直接進行批量移動，消耗 $x$ 天，大本營剩下 $v$ 個士兵。
士兵數量剛好或不足：根據上述討論，需要 $x + (x - v) = 2x - v$ 天，大本營剩下 $x$ 個士兵。

向右側延伸時同理。

根據左側延伸的長度 $x$ ，計算右側最大可以延伸的長度 $y$

根據前述構造方案，完成左側 $x$ 格的佔據後，剩餘 $rem$ 天，且在大本營 $k$ 處累積了 $left = \max(x, v) = \max(x, 1)$ 名士兵。

我們可以根據剩餘天數 $rem$ 與 $left$ 的關係，反推能達到的最大 $y$ ：

若 $rem \le left$ ，則 $y = rem$ 。
若 $rem > left$ ，由於此時必有 $y \ge left$ ，套用公式得 $y \le \lfloor \frac{rem + left}{2} \rfloor$ 。

最終 $y$ 還需滿足 $y \le R = n - k$ （右側邊界限制）。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，我們只需枚舉左側長度 $x$ ，計算過程為 $\mathcal{O}(1)$ 。
空間複雜度： $\mathcal{O}(1)$ 。

Code

def solve():
    n, m, k = map(int, input().split())

    L = k - 1
    R = n - k

    ans = 0
    for x in range(L + 1):
        rem, v = m, 1
        rem -= x if x < v else (2 * x - v)
        left = v if x < v else x
        if rem < 0:
            break
        y = rem if rem <= left else (rem + left) // 2
        ans = max(ans, x + min(y, R) + 1)
    print(ans)

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

寫在最後

PROMPT

masterpiece, best quality, high quality, good quality, 32K UHD, colorful, official art, illustration, in the style of fashion photography, dynamic, dynamic force picture, (Visual impact:1.2), impactful picture, extreme aesthetic, A shot with tension, sharp focus, The Ninth Art, depth of field, cinematic lighting, light particles, lens flare, movie perspective, (Tyndall Effect:1.4), light particles, light, shadow, scenery, temperate atmosphere, (artist:pigeon666:0.83), (Yomu:0.4), (remsrar:0.45), (quasarcake:0.3),

1girl, solo, Nijika Ijichi (ijichi nijika, bocchi the rock), brown eyes, blonde hair, long hair, very long hair, bangs, side ponytail, school uniform, white shirt, pleated skirt, long sleeves, bow, ahoge, sidelocks, outdoors, collared shirt, bowtie, black skirt, bag, red bow, red bowtie,

holding umbrella, transparent umbrella, rain, raining, night, wet street, puddle, reflection, glowing vending machine, backlighting, neon lights, urban scenery, wide shot, landscape, horizontal, looking at viewer, blush

賽時在計算 $left$ 時，沒有考慮 $x=0$ 的情況（因為初始值 $v=1$ 所以要考慮 $x=0$ 的情況），調了好久才發現。