链接:http://acm.hdu.edu.cn/showproblem.php?pid=6301
给出m个区间,要求构造一个指定区间内的数字不能相等,并且数字在$[1,n]$之间,求构造的字典序最小的方案。
首先给区间排个序,按照左端点小、右端点小的规则排。接下来维护两个指针L、R,从左到右往里塞,然后用类似莫队的更新方法去维护数列,同时维护目前可用的数字。 整体复杂度为$O(n+m)$。
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
|
using namespace std;
using Node = struct { int l, r; }; const int maxn = 100100; int n, m, a[maxn]; Node p[maxn]; set<int> st;
signed () { int T; scanf("%d", &T); while(T--) { st.clear(); scanf("%d%d",&n,&m); for(int i = 1; i <= m; i++) { scanf("%d%d",&p[i].l,&p[i].r); } sort(p+1, p+m+1, [](Node a, Node b) { return a.l == b.l ? a.r < b.r : a.l < b.l; }); for(int i = 1; i <= n; i++) { st.insert(i); a[i] = 1; } int L = p[1].l, R = p[1].r; for(int i = L; i <= R; i++) { a[i] = *st.begin(); st.erase(a[i]); } for(int i = 2; i <= m; i++) { while(L < p[i].l) { st.insert(a[L++]); } while(R < p[i].r) { if(R + 1 < p[i].l) R++; else { a[++R] = *st.begin(); st.erase(a[R]); } } } for(int i = 1; i <= n; i++) { printf("%d%c", a[i], " n"[i==n]); } } return 0; }
|
近期评论