經過了一個似乎平安的晚上...
「喔膩醬...」你身邊的祈說道
「我還不知道喔膩醬叫什麼名字耶」
「啊...我叫小志(jizzin)」
「恩!還有跟喔膩醬說喔,我的姓是「天」喔,不過喔膩醬直接叫我名字就好」
祈繼續說到,
「那個,感謝喔膩醬救了我一命,我決定給喔膩醬一個特別的獎勵喔」
「喔喔喔!這個蘿莉果然沒有白撿回來!我的內心,內心的某個深處絕醒了啊啊啊啊!!」你暗爽著。
「那你到底要給我什麼獎勵呢?」你心中早已幻想過數種情況。
「呵呵,那就要看我有多喜歡喔膩醬囉。」
「為了男人的尊嚴,我...我一定要攻略下這隻小蘿莉。」
因此你決定利用這段時間好好增加對祈的好感度
你想到了有N種事情可以做(如:跟她說故事、餵她吃棒棒糖或是一起做體操等等),第i種事情可以增加好感度a_i 。
當然,做太多事也是會累的,因此當你第i種事情放在第j個來做時,你實際上對祈的好感度只會增加a_i −j。
你要選那些事情來做並要如何決定順序,才能增加最多好感度呢?
第一行有一個正整數T,代表有T筆測資。
每個測資的第一行有一個正整數N代表有多少種事情可以做,第二行有N個正整數,第i個數代表a_i ,即做第i件事情的好感度。
對於每筆測資輸出一行,包含一個數字,代表好感度增加的最大值。
對於範例測資的第一筆輸入,你可以先做第4件事,獲得4−1=3的好感度,再做第5件事,獲得5−2=3的好感度,而得到最大值6。
第二筆輸入,你乾脆不要做任何事。
第三筆輸入你可以依序作第2,5,4件事。
對於所有測試資料 : ai≤104
測資組A : T≤20,N≤10
測資組B : T≤20,N≤50
測資組C : T≤20,N≤3000
測資組D : T≤20,N≤105
Step5
No. | Testdata Range | Score |
---|---|---|
1 | 0~1 | 20 |
2 | 2~3 | 20 |
3 | 4~7 | 45 |
4 | 8~9 | 15 |