CF739A.Alyona and mex（构造+贪心）1700

题意

题目链接：Problem - A - Codeforces
给出一个$n$，需要构造一个长度为$n$的数组，然后又$m$个区间$\lbrack l_i,r_i\rbrack$，要满足这若干个区间中最小值最大，并且输出这个值。
数据范围$1\leq n,m\leq 10^5$。

5 3
1 3
2 5
4 5

可以构造出$a=\lbrace 1,0,2,1,0\rbrace$，在三个区间的mex分别是$3,3,2$，所以输出是$2$以及这个a数组。

思路

可以贪心构造出，我们需要的值就是区间长度的最小值$ans$，我们只需要构造出$0,1,2,...,ans-1,0,1,2,...,ans-1,0,1...$

例如加入区间长度最小值是5，我们就能构造出$\lbrace 1,2,3,4,0,1,2,3,4,0,1,2,3,... \rbrace $。为什么能够这样做？因为我们选出任意一个大于区间5的长度的数，都满足条件，哪怕是任意一个地方等于5，例如我在中间随便选取一段：

$\lbrace 1,2,3,4,0,1,\underline{2,3,4,0,1},2,3,... \rbrace $ 你会发现选取出来的$\lbrace 2,3,4,0,1\rbrace$也是满足$mex=5$

代码

inline void Case_Test()
{
    cin>>n>>m;
    ans = inf;
    for (int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        ans = Min(ans,r-l+1);
    }
    cout<<ans<<endl;
    for (int i=1;i<=n;i++)
        cout<<i%ans<<" ";
}