HDU 6301 Distinct Values 【贪心】【模拟】

发表于 | 更新于 | 分类于

题目大意：

找出n个数，满足给出的m个区间内的数都不相同。问满足条件的字典序最小的序列是多少。

解题思路：

字典序最小，说明肯定要越小的越往前填，如果没有限制区间的话答案就是$n$个$1$啦，加上后最先出现的区间要最先考虑，即$l_1$ ~ $r_1$内的数为$1$ ~ $r_1 - l_1$，后面的根据出现的顺序(指填到x时最先覆盖x的区间)依次从小往大填就好了。
题目的难点就是填数时保证不重复。为了改变区间的顺序，肯定要先排序，排序是根据$l_i$为关键字。排序后模拟填数的过程：碰到区间就改变填的数的值，填数时要记录用过的数字，区间结束记得将区间覆盖不到的点再“收回”。而这个所需要的容器可以用优先队列或者set，想到合适的容器就简单多了。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
const int MAX = 1e5+5;

int t, n, m, L, R, res[MAX];
struct node
{
    int l, r;
}a[MAX];
bool cmp(node u, node v)
{
    if(u.l == v.l)
        return u.r < v.r;
    return u.l < v.l;
}
set<int> S;
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n,&m);
        for(int i = 0; i < m; ++i)
            scanf("%d%d", &a[i].l, &a[i].r);
        sort(a, a + m, cmp);
        S.clear();
        for(int i = 1; i <= n; ++i)
        {
            res[i] = 1;
            S.insert(i);
        }
        L = a[0].l, R = a[0].r;
        for(int i = L; i <= R; ++i)
        {
            res[i] = *S.begin();
            S.erase(S.begin());
        }
        for(int i = 1; i < m; ++i)
        {
            while(L < a[i].l)
            {
                S.insert(res[L++]);
            }
            while(R < a[i].r)
            {
                ++R;
                if(R < L)   continue;
                res[R] = *S.begin();
                S.erase(S.begin());
            }
        }
        for(int i = 1; i <= n; ++i)
            printf("%d%c", res[i], i == n ? '\n' : ' ');
    }
    return 0;
}
Donate comment here
0%