大致題意：給定$n$個區間$(l_i,r_i)$。每次選取兩個尚未被標記的區間$(l_1,r_1)$與$(l_2,r_2)$，使得他們均被標記，同時可以任選$x\in [l_1,r_1]，y\in [l_2,r_2]$，然后產生一個新的被標記的區間$(min(x,y),max(x,y))$。問總的被標記的區間的長度最大可以為多少。一個被標記的區間$(l_i,r_i)$的長度為$r_i?l_i$。如果最后剩下一個未被標記的區間，則對其單獨標記，并且不產生新區間。
解：
首先如果$n$是偶數，那么所有區間都會被標記，此時我們就看如何選取會使得新產生的區間長度總和盡可能長。貪心的選擇，對于兩個區間，新產生的區間的端點一定是原來兩個區間的端點，即一個區間的左端點和另一個區間的右端點，這樣盡可能的長。進而考慮：除去基本的區間長度，為了使得新產生區間盡可能長，每個區間要么貢獻$?l_i$，要么貢獻$r_i$，并且最后總共一定是$\frac{n}{2}$個$r_i$以及$\frac{n}{2}$個$l_i$。由此自然想到：取最大的$r_i$以及最小的$l_i$。但是，如果當前$r_i$和$l_i$是同一個區間就不行了。換個思路：我們假設所有的區間一開始都選擇貢獻$r_i$，然后我們要選擇一半的區間，其貢獻由$r_i$變為$?l_i$，其對總貢獻增加了$?(l_i+r_i)$。此值一定為負數，那么考慮其怎么才能最小，即：對$l_i+r_i$排序，選最小的即可。

	int n;cin >> n;vector<pii > a(n + 1);vector<pii > b(n + 1);int ans = 0;for (int i = 1; i <= n; i++) {cin >> a[i].first >> a[i].second, b[i].first = a[i].first + a[i].second;ans += a[i].second - a[i].first;ans += a[i].second;b[i].second = i;}sort(b.begin() + 1, b.end());if (n % 2 == 0) {for (int i = 1; i <= n / 2; i++)ans -= b[i].first;cout << ans << endl;}

接著考慮如果$n$是奇數。前面大致思想都一樣，就是最后一定會剩下一個區間是獨立的。我們直接考慮枚舉最后剩下的區間是哪個，然后取最值即可。

	else {vector<int> pre(n + 1);for (int i = 1; i <= n; i++)pre[i] = pre[i - 1] + b[i].first;int ori = ans;ans = ori - a[b[1].second].second - (pre[1 + n / 2] - pre[1]);for (int i = 2; i <= n; i++) {int re = min(i - 1, n / 2);int ne = n / 2 - re;if (ne <= 0) {ans = max(ans, ori - a[b[i].second].second - pre[re]);} else {int ed = i + 1 + ne - 1;ans = max(ans, ori - a[b[i].second].second - pre[re] - (pre[ed] - pre[i]));}}cout << ans << endl;}