题解：P11109 [ROI 2023] 会议 (Day 2)

· · 题解

原题链接

题意简述

有 n 个区间（n 是偶数），要求选出 \frac n2 个区间，满足其最小点覆盖刚好是原先 n 个区间最小点覆盖的一半（满足原先 n 个区间最小点覆盖也是偶数）。

解题思路

妙妙题。

首先考虑我们该如何选择区间，经典对区间右端点排序并贪心选择。

注意到在选区间的过程中，两两被选择的区间 l,r 之间，编号为 [l+1,r-1] 的区间只要 l 被选择了，一定不会被选择。

因此我们只要在初始的 m 个区间中选出 \frac m2 个作为最后被选的区间，这 \frac m2 个区间各自的后继一定数量的区间一定可以被选中为 \frac n2 个区间之一并不影响最终选择的区间。

由于我们要取的是 \frac n2 个，因此这 m 个区间中一定有 \frac m2 个区间满足后继可扩展的区间数量之和 >\frac{n-m}2。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int T , n , nxt[N];
vector <int> v , ans;

struct point{int l , r , id;} p[N];

signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 1 ; i <= n ; i++) cin >> p[i].l >> p[i].r , p[i].id = i;
        sort(p + 1 , p + n + 1 , [](point x , point y){return x.r < y.r;});
        int lst = 0; v.clear();
        for(int i = 1 ; i <= n ; i++) if(p[lst].r < p[i].l)
        {
            if(lst) nxt[lst] = i;
            v.emplace_back(i) , lst = i;
        }
        nxt[lst] = n + 1; ans.clear();
        // for(auto x : v) cout << x << ' '; cout << '\n';
        sort(v.begin() , v.end() , [](int x , int y){return nxt[x] - x > nxt[y] - y;});
        for(int i = 0 ; i < v.size() >> 1 ; i++) ans.emplace_back(v[i]);
        for(int i = 0 ; i < v.size() >> 1 ; i++)
        {
            if(ans.size() == n >> 1) break;
            for(int j = v[i] + 1 ; j < nxt[v[i]] ; j++)
            {
                ans.emplace_back(j);
                if(ans.size() == n >> 1) break;
            }
        }
        for(auto x : ans) cout << p[x].id << ' '; cout << '\n';
    }
    return 0;
}