CF739A Alyona and mex 题解

题目
简单构造，首先我们知道一个区间 \([l,r]\) 内的最大答案为为这个区间的长度 \(len\)，因为其中可以包括 \([0,r-l+1]\) 这些数。所以 \(ans=min(len_i)\)。

考虑如何满足这个条件，设最小长度为 \(len_{min}\)，我们可以轮流输出 \([0,len_{min}]\)，因为 \(len_{min}\) 是最小长度，所以可以保证每个区间内都存在 \([0,len_{min}]\) 这些数。

#include<bits/stdc++.h>
#define endl '\n'
inline int read(){
    char ch=getchar();int x=0,f=1;
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
int main(){
    //freopen("in.in","r",stdin),freopen("out.out","w",stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),std::cout.tie(0);
    int n=read(),m=read(),ans=1e9;
    for(int i=1;i<=m;++i){
        int a=read(),b=read();
        ans=std::min(ans,b-a+1);
    }
    int p=0;
    std::cout<<ans<<'\n';
    for(int i=1;i<=n;++i){
        std::cout<<(p%=ans)<<' ';p++;
    }
}

赛时降智，想复杂了，耻辱。