题目地址http://acm.hdu.edu.cn/showproblem.php?pid=6301
题意:先给一个T,有T个测试
然后给出n和m,接下来m行是m个事实,每行是一个【l,r】区间,这区间里的数必须各不相同
要你输出字典序最小的n个元素的数组的每一个元素。
题解:
如果要求10个数,1到10 不同,也就是n=10,m=1,l=1,r=10,那么答案显然是
1 2 3 4 5 6 7 8 9 10
问题就在于区间多了,会重,如何给出最小的呢。
对区间处理,用set维护(由于set里元素自动排序且唯一)
定义一个l,一个r.初始等于排完序的结构体的第一个l和r.
结构体按照l小的在前,相等r小的在前排序。
然后ans数组是答案,从l到r赋值1到 每次加加。。。然后set中的值要删除
最后开始处理m-1个(从2到m,第一个是初始情况)fact
如果小区间被包含跳过这一次,这里的l 和 r就像指针一样指,然后ac
#include <iostream> #include <bits/stdc++.h> using namespace std; const int maxn=100005; typedef struct NODE{ int l,r; bool operator < (const NODE &b) const{ if(l==b.l)return r<b.r; else return l<b.l; } }; NODE node[maxn]; int ans[maxn]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d %d",&n,&m); set<int> s; for(int i=1;i<=n;i++) { s.insert(i); ans[i]=1; } for(int i=1;i<=m;i++) { scanf("%d %d",&node[i].l,&node[i].r); } sort(node+1,node+1+m); int l=node[1].l; int r=node[1].r; for(int i=l;i<=r;i++) { ans[i]=*s.begin(); s.erase(s.begin()); } for(int i=2;i<=m;i++) { if(node[i].l>=node[i-1].l&&node[i].r<=node[i-1].r)continue; while(l<node[i].l) { s.insert(ans[l++]); } while(r<node[i].r) { if(r>=node[i].l-1) { ans[++r]=*s.begin(); s.erase(s.begin()); } else{ r++; } } } for(int i=1;i<=n-1;i++) printf("%d ",ans[i]); printf("%d\n",ans[n]); }
return 0; }