回『原創/不分類題庫』
c179: A.門票
標籤 :

通過比率 : 83% (19 人 / 23 人 ) (非即時)
評分方式: Strictly , 記憶體限制: 256 MB
公開 測資點 1 (4%): 1.0s , <1K
公開 測資點 2 (4%): 1.0s , <1K
公開 測資點 3 (4%): 1.0s , <1K
公開 測資點 4 (4%): 1.0s , <1K
公開 測資點 5 (4%): 1.0s , <1K
公開 測資點 6 (4%): 1.0s , <1K
公開 測資點 7 (4%): 1.0s , <1K
公開 測資點 8 (4%): 1.0s , <1K
公開 測資點 9 (4%): 1.0s , <1K
公開 測資點 10 (4%): 1.0s , <1K
公開 測資點 11 (4%): 1.0s , <1K
公開 測資點 12 (4%): 1.0s , <1K
公開 測資點 13 (4%): 1.0s , <1M
公開 測資點 14 (4%): 1.0s , <1M
公開 測資點 15 (4%): 1.0s , <1M
公開 測資點 16 (5%): 1.0s , <1M
公開 測資點 17 (5%): 1.0s , <1M
公開 測資點 18 (5%): 1.0s , <1M
公開 測資點 19 (5%): 1.0s , <1M
公開 測資點 20 (5%): 1.0s , <1M
公開 測資點 21 (5%): 1.0s , <1M
公開 測資點 22 (5%): 1.0s , <1M
公開 測資點 23 (5%): 1.0s , <1M
最近更新 : 2017-04-03 16:29

內容 :

  歡迎來到105學年度下學期校內程式設計競賽。今天,你/妳要幫故事中的主角小Y解決一系列的問題喔。順帶一提,你現在所處的國家,名子就叫做延平國!

 

  身為高中生的小Y,在經歷過悲慘期考之後,找了N個同學(包含小Y自己),準備去延平國裡面的延平遊樂場遊玩。在延平國這個奇怪的國家中,市面上的紙鈔擁有高達2*109種,每種的面額分別是1, 2, 3, …… , 2*109-1, 2*109。而且,在這個國家中,付錢超過面額,是不會找零錢、紙鈔的,也就是說,假設今天有一個1234塊的商品,如果你付5678塊,延平國的商店是不會找你4444元的。

 

  現在,小Y到了延平遊樂園的門口,發現每個人要付的門票費是不一樣的!每個人所對應到的門票費分別是a1, a2, ……, aN-1, aN,並且所有門票都是由一個自動售票機販售的。

 

  這個售票機的收費方式是這樣:你先放一張價值p的鈔票進去售票機,售票機會先把價值p的鈔票轉變成價值p的儲值卡,之後售票機會自動幫你用這張儲值卡,去付門票費。售票機從還沒被付到錢的門票費中,編號最小的(也就是最所有沒有被付到錢的ai中,挑出i最小的)開始,依序付款。只要這張儲值卡的餘額比即將要付的門票的價格還低時,售票機就會自動銷毀這張儲值卡,並且要求你再放一張鈔票進去。

 

  現在,已知小Y手頭上有k張鈔票,並且這k張鈔票的面額都相同。我們想知道,要讓小Y能夠順利買完N個人的門票,這個面額最小需要是多少?

 

  比如說,現在有N=5個人,小Y有k=3張鈔票,每個人所對應到的門票費分別是<1,2,3,4,5>。這個時候,如果小Y手上鈔票的面額都是8,售票機會先用第一張儲值卡付第一、二、三人的錢,第二張儲值卡付第四個人的錢,用第三張儲值卡付第五個人的錢。而如果鈔票面額是6,小Y還是可以付完這五個人的門票錢,而6也恰好是最小所需要的面額。

輸入說明 :

  第一行有兩個正整數Nk(1≤kN≤2*105),分別代表小Y和他同學的總人數與小Y手上有幾張鈔票。

  接下來的的一行有N個整數a1, a2, ……, aN(1≤ai≤10,000),其中ai代表第i個人的門票費。

輸出說明 :

  輸出一個整數於一行,代表鈔票的面額最小需要是多少。

範例輸入 : help
若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
5 3
1 2 3 4 5
範例輸出:
6
提示 :
標籤:
出處:
2016下學期延平中學高中組校內程式設計競賽 (管理:fishtoby)

本題狀況 本題討論 排行