[Codeforces740C]Alyona and mex

传送门

题意

给定长度为n的数组，m个区间，要求构造一个数组（元素大于等于0），求出mex的最小值。
mex：区间里没有出现的最小元素（大于等于0）
并使mex尽量大

思路

一个重要的特点： 一个数组的mex取决于给定区间的长度，数组中最小的mex等于给定区间的最短长度。
证明：要尽量使mex尽量大，最短区间的数字只能从0开始递增，这时mex的值就为区间的长度

因此原数组只要照[0,1,…,mex-1]的规则从左至右构造下去即可，这样就使得给定的每组区间的mex相等且mex尽量大

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int n, m, l, r, k = INF;
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> l >> r;
		k = min(r - l + 1, k);
	}
	cout << k << endl;
	for (int i = 0; i < n; i++)
		cout << i % k << " ";
	return 0;
}

留言

2017-01-12
⬆︎TOP