Yu-Cheng Huang amoshyc

PTC 2015/12_1 C: Warehouse

比賽時，記憶體並沒有限制，題目放上 etutor 後，記憶體有 64MB 的限制，造成 next 陣列開不出來（etutor 竟然把 MLE 回報成 TLE…）。現在有新增第二筆測資，N <= 500，這樣就能在 64MB 的限制下解出該筆測資。

給定一些物品的價值與重量，在滿足 Wa <= 總重 <= Wb 的條件下，選至少 L 個物品出來，並使單位重量的價值 ceil(sum(w) / sum(v) 最大化。

乍看之下很像可以用二分搜解的平均最大化的問題，但仔細分析可以發現，新增加的條件會造成二分搜解法中的單調性消失，所以不能使用二分搜來解這題。

以下出現 A[l, r] 代表 A 陣列中 [l, r] 這個區間。同理 A[l, r) 代表 A 陣列中 [l, r) 這個區間。

以下範例皆不處理 IO 的部份，都假設變數皆已被讀入。

大一時學過，我們可以用二分搜在一個單調（遞增或遞減）的陣列中，尋找某個值在哪裡：

K lengths of cable for free 這是指「K 條 cable 免費」，而不是「長度大於 K 的免費」…

觀察可得，當我們確定 longest remaining cable = L 時，我們可以用最短路徑演算法得到此時從 0 走到 N-1 最少需要幾條 > L 的邊（d[N-1]），

上一題 poj 3276 的簡化（K=3）與小變形（首尾可反轉二個）

相當於只能反轉連續三個，並且反轉區間的頭從 -1 開始直到 N-2（不是 N-3），

書上例題…… 枚舉 + 貪心（dp）

我們枚舉 K，看 K 固定時需要多少次反轉次數，最直覺的寫法是：

尋找一個連續區間，他們的平方和等於 q，問這種區間有幾個，分別是那些區間……

爬行法輕鬆解

爬行法…

先建質數表，然後在質數表上爬行。

※ 以下都是我自己著墨出來的，不保證正確

※ 以下 r+ 指的是比 r 大的數

	# Your init script
	#
	# Atom will evaluate this file each time a new window is opened. It is run
	# after packages are loaded/activated and after the previous editor state
	# has been restored.
	#
	# An example hack to log to the console when each text editor is saved.
	#
	# atom.workspace.observeTextEditors (editor) ->
	# editor.onDidSave ->