轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年2月26日 星期三

STEP5::Problem 0006 : Ch1-3.陷阱

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0006
不知道分哪類......。
題目是要讓1~任意點的區間和大於0,每次可以讓一個點+1或是將最後的點移到前面,問最少步數。

CODE真的好醜,應該有更好的寫法......
我的方法是,先將全部加起來(p),並記錄最小的區間和是多少(q),這個點離尾端多遠(S),然後判斷,如果p小於0就看要加多少才會到1,這些是一定要花費的步數(不然去哪裡搬更大的數字??),再來看看修好的陷阱壓不壓得過q(如果負太多修了也沒用),壓的過就直接輸出了,但如果壓不過就表示好的陷阱都在S那段,那就要判斷把S這段搬過來跟修好q差多少,也就是要修陷阱還是搬陷阱會比較快,(把S全搬到前面一定可以壓過q)。