文章目錄

• • @[toc]
  • • 試題編號
    • 試題名稱
    • 時間限制
    • 內存限制
    • 問題描述
    • 輸入格式
    • 輸出格式
    • 樣例輸入1
    • 樣例輸出1
    • 樣例解釋
    • 樣例輸入2
    • 樣例輸出2
    • 樣例解釋
    • 子任務
    • `Python`實現

試題編號

---

試題名稱

---

時間限制

---

內存限制

---

問題描述

• 頓頓總共選中了$n$塊區域準備開墾田地，由于各塊區域大小不一，開墾所需時間也不盡相同。據估算，其中第$i$塊$(1\le i\le n)$區域的開墾耗時為$t_i$天，這$n$塊區域可以同時開墾，所以總耗時$t_{Total}$取決于耗時最長的區域，即：

t T o t a l = max ? { t 1 , t 2 , ? , t n } t_{Total} = \max\set{t_{1} , t_{2} , \cdots , t_{n}} tTotal?=max{t1?,t2?,?,tn?}

• 為了加快開墾進度，頓頓準備在部分區域投入額外資源來縮短開墾時間，具體來說：
  • 在第$i$塊區域每投入$c_i$單位資源，便可將其開墾耗時縮短$1$天
  • 耗時縮短天數以整數記，即第$i$塊區域投入資源數量必須是$c_i$的整數倍
  • 在第$i$塊區域最多可投入$c_i\times (t_i?k)$單位資源，將其開墾耗時縮短為$k$天
  • 這里的$k$表示開墾一塊區域的最少天數，滿足 0 < k ≤ min ? { t 1 , t 2 , ? , t n } 0 < k \leq \min\set{t_{1} , t_{2} , \cdots ,t_{n}} 0<k≤min{t1?,t2?,?,tn?}；換言之，如果無限制地投入資源，所有區域都可以用$k$天完成開墾
• 現在頓頓手中共有$m$單位資源可供使用，試計算開墾$n$塊區域最少需要多少天

---

輸入格式

• 從標準輸入讀入數據
• 輸入共$n+1$行
• 輸入的第一行包含空格分隔的三個正整數$n$、$m$和$k$，分別表示待開墾的區域總數、頓頓手上的資源數量和每塊區域的最少開墾天數
• 接下來$n$行，每行包含空格分隔的兩個正整數$t_i$和$c_i$，分別表示第$i$塊區域開墾耗時和將耗時縮短$1$天所需資源數量

---

輸出格式

• 輸出到標準輸出
• 輸出一個整數，表示開墾$n$塊區域的最少耗時

---

樣例輸入1

4 9 2
6 1
5 1
6 2
7 1

---

樣例輸出1

5

---

樣例解釋

• 如下表所示，投入$5$單位資源即可將總耗時縮短至$5$天，此時頓頓手中還剩余$4$單位資源，但無論如何安排，也無法使總耗時進一步縮短

$i$	基礎耗時	$t_i$縮減$1$天所需資源	$c_i$投入資源數量	實際耗時
$1$	$6$	$1$	$1$	$5$
$2$	$5$	$1$	$0$	$5$
$3$	$6$	$2$	$2$	$5$
$4$	$7$	$1$	$2$	$5$

---

樣例輸入2

4 30 2
6 1
5 1
6 2
7 1

---

樣例輸出2

2

---

樣例解釋

• 投入$20$單位資源，恰好可將所有區域開墾耗時均縮短為$k=2$天；受限于$k$，剩余的$10$單位資源無法使耗時進一步縮短

---

子任務

• $70\%$的測試數據滿足：$0<n$，$t_i$，$c_i\le 100$且$0<m\le 10^6$
• 全部的測試數據滿足：$0<n$，$t_i$，$c_i\le 10^5$且$0<m\le 10^9$

---

Python實現

n, m, k = map(int, input().split())days = []
for _ in range(n):days.append(list(map(int, input().split())))def judge(x):sum = 0for i in range(n):if days[i][0] < x:continuesum += (days[i][0] - x) * days[i][1]if sum <= m:return Trueelse:return Falsel, r = k, max(days, key=lambda x: x[0])[0]while l <= r:mid = (l + r) // 2if judge(mid):r = mid - 1else:l = mid + 1print(l)

---