[CF555B] Case of Fugitive

[CF555B] Case of Fugitive - 贪心

Description

(n) 个区间，互不相交，(m) 条线段排好序，一条线段连接两个区间当且仅当线段的两个端点分别在两个相邻的区间内，问是否能将所有区间连通

Solution

先按 r 排序，r 相同按 l，均为升序，每次贪心选择合法的 l 最小的

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

#define int long long

const int N = 1e6 + 5;

int n, m, a[N], l[N], r[N], ans[N];

struct segment
{
    int l, r, id;
    bool operator<(const segment &rhs) const
    {
        if (r == rhs.r)
            return l < rhs.l;
        else
            return r < rhs.r;
    }
} s[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i] >> r[i];
        if (i > 1)
        {
            s[i - 1].l = l[i] - r[i - 1];
            s[i - 1].r = r[i] - l[i - 1];
            s[i - 1].id = i - 1;
        }
    }
    sort(s + 1, s + n);
    set<pair<int, int>> ms;
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        ms.insert({x, i});
    }

    for (int i = 1; i < n; i++)
    {
        int l = s[i].l, r = s[i].r;
        auto it = ms.lower_bound({l, 0});
        if (it == ms.end())
        {
            cout << "No" << endl;
            return 0;
        }
        if (it->first > r)
        {
            cout << "No" << endl;
            return 0;
        }
        ans[s[i].id] = it->second;
        ms.erase(it);
    }
    cout << "Yes" << endl;
    for (int i = 1; i < n; i++)
        cout << ans[i] << " ";
}