18年暑假多校赛第一场 1004

题目地址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; }