Codeforces Round #381 (Div. 1) A. Alyona and mex 构造
A. Alyona and mex
题目连接:
http://codeforces.com/contest/739/problem/A
Description
Alyona's mother wants to present an array of n non-negative integers to Alyona. The array should be special.
Alyona is a capricious girl so after she gets the array, she inspects m of its subarrays. Subarray is a set of some subsequent elements of the array. The i-th subarray is described with two integers li and ri, and its elements are a[li], a[li + 1], ..., a[ri].
Alyona is going to find mex for each of the chosen subarrays. Among these m mexes the girl is going to find the smallest. She wants this minimum mex to be as large as possible.
You are to find an array a of n elements so that the minimum mex among those chosen by Alyona subarrays is as large as possible.
The mex of a set S is a minimum possible non-negative integer that is not in S.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 105).
The next m lines contain information about the subarrays chosen by Alyona. The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), that describe the subarray a[li], a[li + 1], ..., a[ri].
Output
In the first line print single integer — the maximum possible minimum mex.
In the second line print n integers — the array a. All the elements in a should be between 0 and 109.
It is guaranteed that there is an optimal answer in which all the elements in a are between 0 and 109.
If there are multiple solutions, print any of them.
Sample Input
5 3
1 3
2 5
4 5
Sample Output
2
1 0 2 1 0
Hint
题意
给你n个数,然后m个区间,你需要构造n个数,使得这m个区间的mex最小值最大。
题解:
其实只和区间长度有关,你按照0123......0123这样去构造,那个区间总能够包含0到那么多的数的。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
scanf("%d%d",&n,&m);
int ans = n;
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
ans = min(ans,r-l+1);
}
cout<<ans<<endl;
for(int i=0;i<n;i++){
cout<<i%ans<<" ";
}
cout<<endl;
}
最新文章
- ANGULAR JS WATCH监听使用(详)
- ReactNative真机运行指南
- Thinkphp框架感悟(一)
- 清除mstsc远程登录记录
- hook_schema 小总结
- hdu_5276
- (摘)Chart Y轴设置为百分比
- [置顶] java 通过classloader加载类再通过classforname实例化
- SQL Syscolumns
- VBOX安装Centos设置分辨率为1366x768[已解决]
- EL表达式与三目运算符
- VR一体机如何退出FFBM
- TCP与UDP区别总结
- mkfs.ext4快速格式化大容量硬盘
- Scala - 快速学习08 - 函数式编程:高阶函数
- 2545 ACM 博客 比较树的路径长短
- 详谈再论JAVA获取本机IP地址
- 使用apidoc 生成Restful web Api文档——新手问题与解决方法
- PAT甲题题解-1127. ZigZagging on a Tree (30)-中序、后序建树
- (C#)计算1-2+3-4+.....+m
热门文章
- CMMI整体理解
- centos 安装flash插件
- 搜索结果高亮显示(不改变html标签)
- jsp_包含指令
- tomcat提供文件下载
- objective-c 创建工程/编译/运行程序
- [Leetcode][JAVA] Longest Consecutive Sequence
- spinner与arrays.xml的使用
- HTTP02--Http请求头及缓存知识
- 应用框架的设计与实现——.NET平台(10 授权服务.CodeAccessSecurityAttribute)