🔗 🔵 ABC389E Square Price

Problem Statement

題目簡述

有 $N$ 種產品，每種庫存無限（ $10^{100}$ 單位）。購買第 $i$ 種產品 $k$ 單位需花費 $k^2 \times P_i$ 日元。給定總預算 $M$ ，求最多能購買的總單位數。

Constraints

約束條件

$1 \leq N \leq 2 \times 10^{5}$
$1 \leq M \leq 10^{18}$
$1 \leq P_i \leq 2 \times 10^{9}$
所有輸入均為整數

思路：二分答案

題型定位

核心考點是二分答案。直接求最多能買多少件並不好下手，但如果反過來固定一個價格門檻，判斷「買下所有邊際成本不超過門檻的商品是否會超出預算」，就能得到一個單調判定。

從暴力出發

最直觀的做法，是把所有商品的單件價格列出來，按價格從小到大購買。但每種產品都有 $10^{100}$ 單位，總商品數量遠遠超出可列舉範圍。

稍微聰明一點，可以用大小為 $N$ 的最小堆維護每種產品目前下一件的價格。每次取出當前最便宜的一件，買下後再把同種產品的下一件放回堆中。不過這仍然只是「逐件購買」的模擬，瓶頸沒有消失：

堆模擬的複雜度瓶頸

假設所有 $P_i = 1$ ，若每種產品都買 $k$ 件，總花費為 $N \cdot k^2 \leq M$ ，因此 $k \leq \sqrt{M/N}$ 。逐件模擬需要約 $k \cdot N$ 次堆操作，複雜度為 $\mathcal{O}(\sqrt{M \cdot N} \log N)$ 。在最大資料範圍下，這個量級可達 $10^{11}$ 以上，無法通過。

關鍵觀察：邊際成本

把平方花費拆開來看。對同一種產品，從買 $j-1$ 件增加到買 $j$ 件，多付出的錢，也就是第 $j$ 件的邊際成本為：

p \cdot \big(j^2 - (j-1)^2\big) = p \cdot (2j - 1)

所以同一種產品的第 $1,2,3,\dots$ 件，其邊際成本依序為 $p,3p,5p,\dots$ ，是一個公差為 $2p$ 的等差數列。也就是說，每種產品內部的購買順序天然按價格遞增。

可遷移套路

遇到「買 $k$ 件的總花費是某個非線性函數」這類題目，可以先看從 $k-1$ 件增加到 $k$ 件的差分。差分後得到的邊際成本往往更容易排序、二分或用資料結構維護。

二分什麼？

接下來不再逐件取最小值，而是二分一個價格門檻 $x$ ：假設買下所有邊際成本 $\leq x$ 的商品，檢查總花費是否不超過 $M$ 。

對於價格係數為 $p$ 的產品，若購買 $k$ 件，則第 $k$ 件的邊際成本必須滿足：

p \cdot (2k - 1) \leq x \quad\Rightarrow\quad k = \left\lfloor \frac{x + p}{2p} \right\rfloor

此時這種產品會買到 $k$ 件，總花費為 $p \cdot k^2$ 。對所有產品加總，就能在 $\mathcal{O}(N)$ 時間內完成一次判定。

單調性保證

門檻越大，會被納入的商品只會變多，總花費也只會不減。因此「買下所有邊際成本 $\leq x$ 的商品後，總花費是否 $\leq M$ 」具有單調性，可以二分最後一個可行門檻。

處理邊界：以 $x+1$ 修正剩餘預算

二分得到最大的可行門檻後，只能保證所有邊際成本 $\leq x$ 的商品都能買完。此時可能還有剩餘預算，能再買一部分邊際成本為 $x+1$ 的商品。

處理步驟：

以 $x+1$ 作為門檻，重新計算總花費與總數量。
由於 $x$ 已經是最大可行門檻，以 $x+1$ 計算出的總花費會超出預算。
多算進來的商品，邊際成本全都是 $x+1$ 。因此把超出金額除以 $x+1$ 並向上取整，就是需要從數量中扣掉的件數。

易錯點

件數公式來自 $p(2k-1) \leq x$ ，不要把它誤寫成 $x/(2p)$ 。
最後扣除超出數量時要向上取整。即使只超出 $1$ 日元，也表示多算進了一件邊際成本為 $x+1$ 的商品。

複雜度分析

時間複雜度： $\mathcal{O}(N \log M)$ $O (N lo g M)$
- 二分搜尋上下界為 $[0, 2^{60}]$ ，共 $\mathcal{O}(\log M)$ 輪
- 每輪檢查需遍歷所有 $N$ 種產品
空間複雜度： $\mathcal{O}(N)$ ，僅需儲存價格陣列

本題要點

把總花費 $k^2$ 做差分，轉成邊際成本 $2k-1$ 。
固定價格門檻後，可以快速算出每種產品能買幾件，形成單調判定。
最大可行門檻只處理到 $x$ ，剩下要用 $x+1$ 的超出量修正答案。

Code

from math import ceil

N, M = map(int, input().split())
P = list(map(int, input().split()))

# 檢查購買所有邊際成本 <= x 的商品時，總花費是否 <= M
def check(x):
    cost = 0
    for p in P:
        # p * (2k - 1) <= x  =>  k = floor((x + p) / (2p))
        k = (x + p) // (2 * p)
        cost += k * k * p
    return cost <= M

# 二分搜尋最大的 x，使得 check(x) 為 True
left, right = 0, 1 << 60
while left <= right:
    mid = (left + right) // 2
    if check(mid):
        left = mid + 1
    else:
        right = mid - 1

x = right          # 最大可行門檻
ans = cost = 0
for p in P:
    # 以 x+1 為門檻計算，此時總花費可能超過 M
    k = ((x + 1) + p) // (2 * p)
    cost += k * k * p
    ans += k

# 超出預算的部分，每件商品價格都是 x+1
more = cost - M
ans -= ceil(more / (x + 1))
print(ans)