P9925 [POI 2023/2024 R1] Zapobiegliwy student 题解

phoenixzhan · 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;
}