COCI-2011/2012#3-6-Traka

題目PDF：http://www.hsin.hr/coci/contest3_tasks.pdf
比賽官網、測資：http://www.hsin.hr/coci/
(克羅埃西亞文Traka -> 英文Tape)

有N個工人組成的生產線，以及要進行的M樣工作(N,M到100000)
每位工人負責的崗位都有複雜度T[i]
每樣工作也有相應的複雜度F[j]
工人i進行工作j需要花T[i]*F[j]的時間(T和F是1...10000的正整數)
現在這個公司有個規定，工人一旦完成工作
一定要立刻交給下一個人並且要馬上開工！
萬一此時下一個人手邊還有工作沒作完，老闆就會爆炸，把全部的員工都火掉

這時候身為工人1號的Mirko有個重要的責任
他可以透過適當的等待一些秒數再工作，來避免相撞(也只有他有權這麼做)
例如下面這條範例測資它會在時刻0開始工作1、時刻4結束、(等待1秒)、時刻5開始工作2...
問最少要花多少時間這N個人依序將M樣工作做完

3 3
2
1
1
2
1
1

答案是11

程式碼(正解[O(nlgn + mlgn)])：待補
程式碼(假解[O(nlgn + mk) , k=9])：http://codepad.org/2W7zOAPW

這道題真的想了很久、收穫很大
前面嘗試過很多奇怪的策略，
好比說挑戰一下隨意交換工人順序看答案有沒有變(顯然會差很多XD)
或者是想想看有沒有辦法O(nm) DP，然後想像有奇怪的優化做到O(nlgm)
想起波利亞大師的話，考慮一下T[]全部都是1的情形、或是F[]全部是1的情形

發現「複雜的工作會擋住簡單的工作，動作快的工人得遷就動作慢的工人」
(但令人失望的這原則並不是絕對成立，只是接近而已)

走到這裡發現這題有很強的最優子結構(前面做的決定，對全局來說也會是最優的決定)
於是大膽的想像他可能和超級難題PKU3666-Making the Grade一樣！
(純記錄文章：http://nphard001.blogspot.com/2011/11/pku3666-making-grade.html)
我們試著把工作速度很快的幾個工人看成一個單位....(ry

費了非常大的力氣(非常佩服400多人中有8位勇士在3小時內做完前五題並且AC這題)
才終於屈服、前面想的很可能都沒什麼關鍵用途！(當然，可以幫助了解題目甚麼的)
來導數學式吧

首先發現狀態只要記錄第一個人工作的狀況就可以代表整體的狀態
設目前剛做完工作j，end[i]是工人i空閒的時刻，
那麼就有end[i]=end[0]+( sigma(k=1...i)T[k] ) * F[j]
因為工人1(註標上是工人0)高超的智慧已經知道要等幾秒或不用等，可以讓後面不相撞
反正後面的人就全部照做就是了
只要總結前幾輪delay了多久，就可以立刻算出全局的答案是多少

觀察後面的測資發現，我們每次決定等幾秒(delay值)的方法，
其實同時也是在決定「要遷就誰」(最基本是遷就工人1，否則工作無法開始)
於是神來一筆地(導這公式花了我好幾個小時...QAQ)
對於(N>i>0)，定義函數f(i)代表如果要讓工人i不發生衝撞，需要delay幾秒
問題轉化成了求i=1...N-1中，哪一個f(i)最大
(選了最大的那個delay，就確保了其他人也能順利工作)

經過無數的巧思時間精力化簡得到(定義目前正在做工作j且j>0、工作0一定不用等)：
f(i) = ( sigma(k=1...i)T[k] ) (F[j-1]-F[j]) + (T[i]-T[0]) (F[j])
好了好了，有這一大串公式可以幹嘛呢
我們現在知道( sigma(k=1...i)T[k] ) 、 (T[i]-T[0])可以預處理
F[j-1]-F[j]以及F[j]都是每一輪過程中的變數

於是我想到一個神奇的假解、決定先實現他：
我們令p=F[j-1]-F[j] , q=F[j]，其中q恆正
因此我們對T[i]排序，知道如果取最大的T[i]能令(T[i]-T[0])q這項最大
但是最大值不一定是仰賴q，也會受到p影響
分開討論當
(1) p=0，最大的T[i]就是答案
(2) p>0，選次大的T[g]就好像在說減一些p、換取一些q (g必須比i大，這樣sigma才會多)
(3) p<0，和上面相反，犧牲一些p、換取在q項被扣比較少(g必須比i小)
於是分開檢查前k個可用的T、後k個可用的T取最大值
k=9的時候，全測資通過，是為假解…(假解一出簡直高興得不得了！這代表正解不遠了)

============================

至於怎麼做正解呢？台大醫科的小乃學長一語點破「計算幾何」
讓我非常快的發現
f(i) = ( sigma(k=1...i)T[k] ) (F[j-1]-F[j]) + (T[i]-T[0]) (F[j])
定義
( sigma(k=1...i)T[k] )=x
(F[j-1]-F[j])=p
(T[i]-T[0])=y
(F[j])=q

求f(i)=px+qy最大值，其中x和y的可能性可以全部預處理
於是這變成了一道線性規劃問題
p,q是不斷改變的利潤函數係數並且有q恆為正
對於N個工人，他們就像座標平面上的N個點、sigma值是x座標、自己的值是y座標
可以預先算出這N個點的凸包，並且只留下上側凸包，
讀入M筆不同詢問的p和q、對上側凸包二分搜尋找最接近的斜率(平行線法)

預先排序求凸包nlgn、有m筆詢問，每次二分搜lgn回答
最終正解複雜度O( (n+m)lgn )、合併起來比較帥

============================

最後我們回頭來檢討為什麼假解可行呢？
其實是T[],F[]範圍的關係：每項都不超過10000，而相對項數卻有10萬項
也因為sigma的關係
用這種方法構造出來的x,y值，整個把畫面拉遠一點看
發現解區域凸包呈狹長型
這點一定程度的提供了我們亂搞的機會
並且測資random的情形下，p和q的差距往往很大(也就是利潤函數長得很陡峭)

對於比較大的測資：狹長多邊形+很陡很簡單的利潤函數，只找前後9個點已經足夠
對於比較小的測資：k個點幾乎就等於把整個凸包上側走過一遍

於是假解得以AC

怎麼構造卡這種假解的測資，
如果把T[],F[]取值範圍加強到long long或許就可以逼得常數k得往上升一些才有是答案

題解完