[TIOJ] 1852. 分眼皮
題目連結: http://tioj.infor.org/problems/1852 有趣的題目XD，看到24先猜砍半枚舉，但想了一段時間才知道該怎麼讓枚舉出來的兩個集合跟答案有關連。 首先發現，假設最後選出來的三個數字分別是$(a, b, c)$(不失一般性假設$a \geq b \geq c$)，也就是說假設在枚舉出來的第一個集合中有一個三元組$(x, y, z)$(沒有大小關係)，那只要在第二個集合中找到$(x^\prime, y^\prime, z^\prime)$使得$x+x^\prime \geq y+y^\prime \geq z+z^\prime$就好。 接著考慮$a-b, c-b$，發現只要$a-b\geq 0 \land c-b \leq 0$就可以代表$a \geq b \geq c$，也就是說對於第一個集合中的$(x, y, z)$，我們就是要找到使得$x+x^\prime-(y+y^\prime) \geq 0 \land z+z^\prime - (y+y^\prime) \leq 0$(也就是$y^\prime - x^\prime \leq x-y \land y^\prime - z^\prime \geq z-y$)成立的$(x^\prime, y^\prime, z^\prime)$中，$x^\prime - z^\prime$最小的那個，因為他就代表$(x, y, z)$可以配出的最小值($x+x^\prime - (z+z^\prime)$)。 這樣，就會發現問題轉換成給你一堆二維帶權資料點($(y^\prime - x^\prime, y^\prime - z^\prime)$, $x^\prime - z^\prime$)，請求出第一維大於等於某個數且第二維小於等於某個數中，值最小的那個。這問題簡單的對一維排序後，加上一些前(後)綴極值資料結構，再利用雙指針就可以解決了 #include <bits/stdc++.h> using namespace std; typedef int64_t lld; const int N = 24; const lld INF = 1LL<<60; class BIT{ private: vector<lld> arr; inl