校门外的树

Posted on Edited on In

题目大意：要求给出一个 N 个数的数列，数列中每个数字的范围为 1 到 N，且数列要满足一系列诸如给定区间[Li,Ri]中没有重复数字的要求，问字典序最小的合法方案是什么

考虑如何合理的给区间排序，显然是按照左端点升序，左端点一样的情况下右端点降序

如果区间有交集，那么重复的肯定不考虑，然后重新得到一个新的区间

暴力的搞一下就可以了

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 66;

int T, n, m, cnt;
int vis[N], res[N];

struct yhzhyhm
{
    int l, r;
    bool operator < (const yhzhyhm &x) const
    {
        return (l < x.l) || ((l == x.l) && r > x.r);
    }
}yh[N], num[N];

inline void yhm_clear()
{
    cnt = 0;
    memset(&yh, 0, sizeof yh);
    memset(&num, 0, sizeof num);
    memset(vis, 0, sizeof vis);
    memset(res, 0, sizeof res);
    return;
}

inline void yhm_func()
{
    int i, j, tmp;
    n = read(), m = read();
    for (i = 1; i <= m; ++ i)
    {
        yh[i].l = read(), yh[i].r = read();
        if (yh[i].l > yh[i].r) swap(yh[i].l, yh[i].r);
    }
    sort(yh + 1, yh + 1 + m);
    int maxr = 0;
    for (i = 1; i <= m; ++ i)
    {
        if (yh[i].r <= maxr) continue;
        num[++ cnt] = yh[i];
        maxr = yh[i].r;
    }

    for (i = 1; i <= cnt; ++ i)
    {
        tmp = 1;
        if (num[i].l > num[i - 1].r) for (j = num[i].l; j <= num[i].r; ++ j) res[j] = tmp ++;
        else
        {
            for (j = num[i].l; j <= num[i - 1].r; ++ j) vis[res[j]] = i;
            for (j = num[i - 1].r + 1; j <= num[i].r; ++ j)
            {
                while (vis[tmp] == i) tmp ++;
                res[j] = tmp; vis[tmp] = i;
            }
        }
    }

    for (i = 1; i <= n; ++ i) put(res[i] ? res[i] : 1);
    return (void)(puts(""));
}

signed main()
{
    T = read();

    while (T --)
    {
        yhm_clear();
        yhm_func();
    }
    
    return 0;
}