自动搬运

查看原文

来自洛谷，原作者为

	phoenixzhan **

搬运于2025-08-24 22:53:05，当前版本为作者最后更新于2024-02-01 11:42:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设最多可以选出 $t$ 条彼此无交的线段（这是个经典的贪心问题），显然我们可以构造出 $t-1$ 组的方案：任取其中一条线段作为其他 $t-1$ 条线段的 pair，于是只需要判断是否有 $t$ 组的方案。

由于最多可以选出 $t$ 条无交线段，考察最后答案的 $t$ 组线段中，一条线段 $u_i$ 和它的 pair $v_i$，显然 $v_i$ 和 $u_i$ 有交，且 $v_i$ 和 $u_{i-1},u_{i+1}$ 无交。有了这些性质，随便贪一贪就可以了。把所有线段按右端点排序，每次选出两条右端点最小的线段作为 $u$ 和 $v$，即可。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
#define int long long
namespace Loser {
	int n;
	struct Seg {
		int fi, se, id;
	} a[500010]; 
	bool cmp(Seg a, Seg b) {
		return a.se == b.se ? a.fi < b.fi : a.se < b.se;
	}
	int cnt; vector<int> ans;
	int tot; vector<pii> res; 
	void main() {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se, a[i].id = i;
		sort(a + 1, a + n + 1, cmp);
		for (int i = 1, r = 0; i <= n; i++) {
			if (a[i].fi < r) continue;
			cnt++; r = a[i].se; ans.pb(a[i].id);
		}
		int pre = 0;
		for (int i = 1, r = 0, R = 0; i <= n; i++) {
			if (a[i].fi < R) {
				if (a[i].fi >= r && !pre) pre = i; continue;
			}
			int k = i + 1;
			if (pre) {
				k = pre; pre = 0;
				tot++, res.pb(mp(a[i].id, a[k].id)); r = R = a[i].se; continue;
			}
			while (k <= n && a[k].fi < r) k++;
			if (k <= n) tot++, res.pb(mp(a[i].id, a[k].id)); r = a[i].se, R = a[k].se; i = k; 
		}
		deb(cnt), deb(tot);
		if (tot >= cnt) {
			cout << tot << '\n';
			for (auto i: res) cout << i.fi << ' ' << i.se << '\n'; return;
		}
		cout << cnt - 1 << '\n';
		for (int i = 1; i < ans.size(); i++) cout << ans[i] << ' ' << ans[0] << '\n';
	}
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1; while (T--) Loser::main(); return 0;
}