f455: 詠竣的哀鳳12
Tags : DP
Accepted rate : 42人/51人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-02-03 23:46

Content

哀鳳推出了第12代,許多人都搶著想買到,詠竣也不例外。然而詠竣的錢並不夠,所以他需要去當臨時工來賺錢。詠竣能拿來打工的時間有限,但是有太多地方在招臨時工了,所以他希望你幫他寫程式計算他最多能賺到多少錢。喔對了,詠竣又小又快(體型小且移動速度快),有學過「神炎光速移動」,所以當他完成一份工作後能夠無縫接軌地直接開始下一份工作,而且他不需要休息!

不過這只是暫時的事情,詠竣對於人生還是希望有點規劃,所以當他完成這次的臨時打工計畫後,他還想到這些工作中時薪最高的地方應徵正式員工,所以請你順便找出時薪最高的工作。

Input

測資為單筆輸入。

第一行有兩個以空白隔開的正整數T、N,代表詠竣有T小時能拿來打工且有N個地方在招臨時工。(T<=10^5、N<=10^4)

接下來N行中,每行有一個字串S和兩個正整數M、H,皆以空白隔開,S代表工作的內容,該份工作需要花費H小時,完成後薪水為M。(M、H<=2×10^5)

Output

第一行請輸出詠竣最多能賺到多少錢。

第二行請輸出N個工作中時薪最高的工作內容。(若答案不只一個,以先輸入的為優先)

Sample Input #1
10 3
印製鯊魚T恤 20 5
用下巴清潔紅土 20 4
賣蘇菜湯 38 10
Sample Output #1
40
用下巴清潔紅土
Sample Input #2
20 3
表演喝下可樂混威士忌後嘔吐 10 20
擔任某高一女孩的男友 10000 22
過來阿姨這邊 500 1
Sample Output #2
500
過來阿姨這邊
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :

範例測資1中,如果詠竣選擇「印製鯊魚T恤」和「用下巴清潔紅土」,總共能賺40元,相較於「賣蘇菜湯」雖然完成後賺到的錢比前兩著都多,但是做完後賺到38元就沒時間了,所以最多能賺到40元。而「印製鯊魚T恤」的時薪為20÷5=4(元);「用下巴清潔紅土」的時薪為20÷4=5(元);「賣蘇菜湯」的時薪為38÷10=3.8(元),所以時薪最高的是「用下巴清潔紅土」。

 2020/12/01 19:44 已將測資中的工作內容全改為英文,並針對Python使用者重測。由於數量太多,所以使用Google翻譯,若有翻譯錯誤,請見諒!

 

如果題目太爛或有出錯,還請不吝告知,感謝!

Tags:
DP
出處:
wseds [管理者:
yes51851823@... (wseds)
]


ID User Problem Subject Hit Post Date
23609
fire5386 (皮卡丘)
f455
動態規劃
295 2020-12-02 20:50