[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;
		inline int lowbit(int x){return x&(-x);}
	public:
		void init(int n){
			arr.resize(n);
			fill(arr.begin(), arr.end(), INF);
		}
		void modify(int p, lld x){
			while(p){
				arr[p] = min(arr[p], x);
				p -= lowbit(p);
			}
		}
		lld query(int p){
			lld ret = INF;
			while(p < (int)arr.size()){
				ret = min(ret, arr[p]);
				p += lowbit(p);
			}
			return ret;
		}
} bit;

class LiSan{
	private:
		vector<lld> vv;
	public:
		void init(){vv.clear();}
		void insert(lld a){vv.push_back(a);}
		void done(){
			sort(vv.begin(), vv.end());
			vv.resize(distance(vv.begin(), unique(vv.begin(), vv.end())));
		}
		int size(){return (int)vv.size();}
		int get(lld x){
			return distance(vv.begin(), lower_bound(vv.begin(), vv.end(), x));
		}
		lld inv_get(int x){return vv[x];}
} lisan;

struct Obj{
	lld a, b, c;
	Obj(lld _=0, lld __=0, lld ___=0): a(_), b(__), c(___){}
};

vector<Obj> A, B;
int arr[N];
void dfs1(int,int,lld,lld,lld);
void dfs2(int,int,lld,lld,lld);

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for(int i=0;i<n;i++) cin >> arr[i];
	A.reserve((int)(pow(3, n>>1)+0.5)); dfs1(0, n>>1, 0, 0, 0); 
	B.reserve((int)(pow(3, n-(n>>1))+0.5)); dfs2(n>>1, n, 0, 0, 0);
	lisan.done(); bit.init(lisan.size()+1);
	sort(A.begin(), A.end(), [](const Obj& a, const Obj& b){
		return a.c-a.b < b.c-b.b;
	});
	sort(B.begin(), B.end(), [](const Obj& a, const Obj& b){
		return a.b-a.c < b.b-b.c;
	});
	lld ans = INF; int p = 0;
	for(auto o : B){
		while(p < (int)A.size() and o.b-o.c >= A[p].c-A[p].b){
			bit.modify(lisan.get(A[p].a-A[p].b)+1, A[p].a-A[p].c);
			p++;
		}
		ans = min(ans, o.a-o.c+bit.query(lisan.get(o.b-o.a)+1));
	}
	cout << ans << '\n';
	return 0;
}

void dfs1(int i, int n, lld a, lld b, lld c){
	if(i == n){
		A.emplace_back(a, b, c);
		lisan.insert(a-b);
		return;
	}
	dfs1(i+1, n, a+arr[i], b, c);
	dfs1(i+1, n, a, b+arr[i], c);
	dfs1(i+1, n, a, b, c+arr[i]);
}

void dfs2(int i, int n, lld a, lld b, lld c){
	if(i == n){
		B.emplace_back(a, b, c);
		return;
	}
	dfs2(i+1, n, a+arr[i], b, c);
	dfs2(i+1, n, a, b+arr[i], c);
	dfs2(i+1, n, a, b, c+arr[i]);
}