c179: A.門票
標籤 :
通過比率 : 80% (24 人 / 30 人 ) (非即時)
評分方式:
Strictly

最近更新 : 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個人的門票費。

輸出說明

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

範例輸入
5 3
1 2 3 4 5
範例輸出
6
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (4%): 1.0s , <1K
公開 測資點#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 , <1M
公開 測資點#13 (4%): 1.0s , <1M
公開 測資點#14 (4%): 1.0s , <1M
公開 測資點#15 (5%): 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
提示 :
標籤:
出處:
2016下學期延平中學高中組校內程式設計競賽 [編輯: fishtoby (瓜瓜) ]
編號 身分 題目 主題 人氣 發表日期
12264 yp155136 (meruru~) c179
binary search
79 2017-06-21 20:12