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<<" ";
}