大致题意：给定nnn个区间(li,ri)(l_i,r_i)(li,ri)。每次选取两个尚未被标记的区间(l1,r1)(l_1,r_1)(l1,r1)与(l2,r2)(l_2,r_2)(l2,r2)，使得他们均被标记，同时可以任选x∈[l1,r1]，y∈[l2,r2]x\in[l_1,r_1]，y\in[l_2,r_2]x∈[l1,r1]，y∈[l2,r2]，然后产生一个新的被标记的区间(min(x,y),max(x,y))(min(x,y),max(x,y))(min(x,y),max(x,y))。问总的被标记的区间的长度最大可以为多少。一个被标记的区间(li,ri)(l_i,r_i)(li,ri)的长度为ri−lir_i-l_iri−li。如果最后剩下一个未被标记的区间，则对其单独标记，并且不产生新区间。
解：
首先如果nnn是偶数，那么所有区间都会被标记，此时我们就看如何选取会使得新产生的区间长度总和尽可能长。贪心的选择，对于两个区间，新产生的区间的端点一定是原来两个区间的端点，即一个区间的左端点和另一个区间的右端点，这样尽可能的长。进而考虑：除去基本的区间长度，为了使得新产生区间尽可能长，每个区间要么贡献−li-l_i−li，要么贡献rir_iri，并且最后总共一定是n2\frac{n}{2}2n个rir_iri以及n2\frac{n}{2}2n个lil_ili。由此自然想到：取最大的rir_iri以及最小的lil_ili。但是，如果当前rir_iri和lil_ili是同一个区间就不行了。换个思路：我们假设所有的区间一开始都选择贡献rir_iri，然后我们要选择一半的区间，其贡献由rir_iri变为−li-l_i−li，其对总贡献增加了−(li+ri)-(l_i+r_i)−(li+ri)。此值一定为负数，那么考虑其怎么才能最小，即：对li+ril_i+r_ili+ri排序，选最小的即可。
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;}
接着考虑如果nnn是奇数。前面大致思想都一样，就是最后一定会剩下一个区间是独立的。我们直接考虑枚举最后剩下的区间是哪个，然后取最值即可。
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;}
)
