2012年3月7日 星期三

UPRC 1151 宴會問題

題目換個說法:A+B+C=m, A>=ai&&B>=bi&&C>=ci, 的數量為MAX
PROCEDURE:
1. 枚舉A(本應枚舉0~10000,但若ai+1>A>ai,則A=ai會更好)-> O(n)
       1) 跑過所有的,把合格的加進來(合格就是A>=ai而且A+bi+ci<=m,第一個很合理,而第二個勒,是因為之後會有m-A-bi要大於ci不然加了也沒有意義,純屬加快用的)
       2) 把合格的進行排序,照b的大小,越大越前面
       3) 接下來,照著b一個一個用BIT查『小於等於m-A-bi』的ci的數量,而且換下一個的時候,就要先刪除這一個,因為儘管那個ci可能很小,但他相連的bi一定會大於之後的bj(由大到小排序)所以不能算進去。
2. 印出解答,然後就AC了,耶XD

ps. bit加一是為了讓他不會壞掉,因為如果是零就會炸掉 boom

http://codepad.org/vUuQP5ai

2 則留言: