內容

溫馨提醒:本題題敘有圖的地方大多是廢話，但可以看一下，歐內該

從之前的題目和各種線索可以合理的推斷出nowob同時是mai眾和vt豚

而這兩個興趣疊加在一個人身上尤其是叫nowob的人身上那肯定是個災難

nowob並不富裕，之前他要依靠偷吃鴨子大將軍從大西洋出征回來時遺留下來的墨西哥蠑螈屍體才能過活

而他現在染上了maimai跟看vt

而他也特別喜歡在機廳搞抽象

像是明明歌名有簡稱，又偏偏喜歡在連機選歌時把整首歌名唸完(如圖)

我是不知道他出於何心，但大概率是因為童年總是喜歡大聲喊出動漫招式覺得自己很帥

除了繼續吃墨西哥蠑螈屍體過活，每天還得到南極的街上蒐集澳大利亞深海仙人掌做成章魚燒再到本基努阿法共和國的廁所外對每個路過的焗烤蜥蜴推銷加熱保溫瓶才能勉強負擔他的龐大開銷

但你可能會想問說，nowob不是很宅嗎?為什麼不在巴哈看免費的番就好了?原因很簡單，第一個他家已經擺了一堆神奇的公仔掛軸等等也花了不少錢了，再加上他看戀愛番看得有點破防，最後是因為這題如果再多一個條件好像會太難我也不知道要怎麼出所以就沒了(如果我突然想到也可能會突然出出來:D)

而nowob現在對於打mai和看vt的上癮狀況都已經進入末期無法克制，他在得知普發一萬後也是直接自動換算成333道+麥香

nowob每天早上起床後都以為會接收到來自上天的弗朗休斯克萊爾夫斯基上尉的爺爺的孫子的隔壁鄰居的小狗的西元114年5月14號的晚餐的寄生蟲的三明治的塔可餅的帽子的指示今天要分別花多少錢在mai還有vt身上

但那其實只是他的妄想，為了合理化他的打mai還有砸錢给vt的行為(畢竟他病的不輕)

而你轉生者你是電你是光你是唯一的神話你是唯一可以拯救nowob這些可怕行為的人

你獲得了一個能力可以強制nowob不打機或是不砸錢在vt上

但你因為剛轉生系統經驗不夠最多只能一天限制他的一個行為(不打機或不花錢在vt上)

且這個次數也是有限的

所以你要判斷如何幫助nowob讓他可以花更少錢

同時為了加強你的系統，請依照以下指示寫出一個強大的程式回報數值給系統升級

有 $\mathbf{N}$ 天
第 $i$ 天若不限制，需花費 $\mathbf{A}_i$(mai)與 $\mathbf{B}_i$(vt)，該日花費為
$$\mathbf{S}_i \;=\; \mathbf{A}_i + \mathbf{B}_i$$
若第 $i$ 天啟用能力(禁止其中一個行為)，則該日花費為
$$\min(\mathbf{A}_i, \mathbf{B}_i)$$

一天最多禁止一個行為，總計最多禁止 $\mathbf{K}$ 天。
目標：在不超過 $\mathbf{K}$ 天使用能力的前提下，最小化「所有天的每日花費最大值」。輸出該最小值記為 $\mathbf{M}$。

輸入說明

第一行：$\mathbf{N}\ \mathbf{K}$
第二行：$\mathbf{A}_1\ \mathbf{A}_2\ \dots\ \mathbf{A}_{\mathbf{N}}$
第三行：$\mathbf{B}_1\ \mathbf{B}_2\ \dots\ \mathbf{B}_{\mathbf{N}}$

輸出說明

一個整數 $\mathbf{M}$，表示在最優策略下，$\mathbf{N}$ 天中的每日花費最大值的最小可能值。

範例輸入

範例一:
5 2
5 3 10 2 8
4 7 1 9 5

範例二:
4 0
3 6 2 1
4 5 7 8

範例三:
6 6
9 2 10 3 5 100
4 8 1 7 5 1

範例輸出

範例一:
11

範例二:
11

範例三:
5

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (50%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <10M

提示：

$0 \le \mathbf{A}_i,\ \mathbf{B}_i \le \mathbf{10}^{\mathbf{9}}$
$1 \le \mathbf{N} \le \mathbf{2}\times \mathbf{10}^{\mathbf{5}}$
$0 \le \mathbf{K} \le \mathbf{N}$

$\mathbf{10}$%：$\mathbf{N} \le \mathbf{22}$，$\mathbf{K} \le \mathbf{N}$，$\mathbf{A}_i,\mathbf{B}_i \le \mathbf{10}^{\mathbf{4}}$。
$\mathbf{20}$%：$\mathbf{N} \le \mathbf{40}$，$\mathbf{K} \le \mathbf{N}$，$\mathbf{A}_i,\mathbf{B}_i \le \mathbf{10}^{\mathbf{6}}$。
$\mathbf{50}$%：$\mathbf{N} \le \mathbf{8000}$，$\mathbf{K} \le \mathbf{N}$，$\mathbf{A}_i,\mathbf{B}_i \le \mathbf{10}^{\mathbf{9}}$。
$\mathbf{20}$%：$\mathbf{N} \le \mathbf{200000}$，$\mathbf{K} \le \mathbf{N}$，$\mathbf{A}_i,\mathbf{B}_i \le \mathbf{10}^{\mathbf{9}}$。

標籤:

二分搜貪心

出處:

[管理者：

louishuang (38024黃禹程)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」