本文共 1556 字，大约阅读时间需要 5 分钟。
给你一段长度为n的区间，然后在给你m个小区间，要求这m个小区间里的每个人都不能重复，请你输出字典序最小的方案.
我们可以开一个suf数组，表示我到我后面的不出现重复数字的区间至少需要到达的位置。所以对于给出的每一个l,r，suf[l] = max(suf[l], r)；
处理好suf数组，在开一个容器，用来表示我现在可以用的数字集合
然后用L变量表示我上一个到达的位置，R变量表示我现在到达的位置。
然后对头扫到尾，如果我现在已经到达的位置比目前 i 的约束条件的位置来的大，说明这个 i 地方我已经判断过了，就可以直接continue到下一步
如果我需要从这个点开始走，那么我就要把这现在这个区间外的值加入到set容器里来，因为这些数对于现在我正在判断的区间是没有影响的。
然后在现在这个区间里每次加入最小的数，然后把这个数从set容器里删除掉
具体看代码
#include#include #include #include #include #include #include #include #include #include #include #include #include #define first fi#define second se#define lowbit(x) (x & (-x))typedef unsigned long long int ull;typedef long long int ll;const double pi = 4.0*atan(1.0);const int inf = 0x3f3f3f3f;const int maxn = 100005;const int maxm = 305;using namespace std;int n, m, tol, T;int suf[maxn];int ans[maxn];void init() { memset(suf, 0, sizeof suf); memset(ans, 0, sizeof ans);}int main() { scanf("%d", &T); while(T--) { init(); scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) suf[i] = i; for(int i=1; i<=m; i++) { int l, r; scanf("%d%d", &l, &r); suf[l] = max(suf[l], r); } int L = 1; int R = 0; set s; s.clear(); for(int i=1; i<=n; i++) s.insert(i); for(int i=1; i<=n; i++) { if(R >= suf[i]) continue; while(L < i) { s.insert(ans[L]); L++; } while(R < suf[i]) { R++; int x = *s.begin(); ans[R] = x; s.erase(x); } } for(int i=1; i<=n; i++) printf("%d%c", ans[i], i==n ? '\n' : ' '); } return 0;}
转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/9357774.html
