## ZJ b793 - I最後的饗宴

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### Subtask 1 : $N ≤ 30$

這個子任務可以枚舉起點然後就一直順時針轉，因為最多轉 $N^2$ 次就會做完，每次暴力檢查是 $O(N)$ ，所以可以做到 $O(N^4)$。

### Subtask 2 : $N ≤ 100$

剛剛的 $O(N^4)$ 看起來不夠過這個範圍，暴力檢查可以優化一下，用串列之類的資料結構紀錄下一個有利的點，可以優化到 $O(N^3)$。

### Subtask 3 : $N ≤ 1000$

$O(N^3)$ 還是不夠快 $QQ$ ，我們發現可以先算出「他拿到第一道菜之後」，要拿完全部的旋轉次數，我們令這個值叫做 $A_i$ ，對於一個人，他拿下一道菜跟上一道菜的距離其實就是 $(next + N - pre)\%N$，而且這個並不與其他人有所衝突，這個計算所需要的時間是 $O(N^2)$，另外我們假設拿到第一道菜時的旋轉次數是 $B_i$ ，不過 $B_i$ 會根據旋轉的起點來改變。

而最後我們可以發現答案就是 $max_{for\ all\ i}(A_i+B_i)$，而我們可以枚舉 $N$ 次起點，而每次計算 $B_i$ 的時間是 $O(N)$，所以也是 $O(N^2)$。最後此問題可在 $O(N^2)$ 內解決。