大于等于 href class 由于 printf .com pre cst
http://codeforces.com/problemset/problem/739/A
对于一个非负整数数列 a,定义 mex(l, r) 为不存在于 a[l]~a[r] 区间内的最小非负整数。
给定数列长度 n,区间个数 m。要求构造一个长度为 n 的数列使得这 m 个区间的最小 mex 最大。
输出 m 个区间的最小 mex,以及构造的数列(多组解时只需要输出一组解即可)
(一开始没看懂题目....)
对于一个长度为 Len 的区间,这个区间的 mex 最大值显然为 Len。
那么现在有 m 个区间,若其中最小区间的长度为 Len,那么即使每个区间的 mex 都能取到最大值,最小 mex 也为 Len。
那么构造数列时只需要保证最小的区间取到最大 mex 即可。
于是可以用 0~Len-1 循环构造数列,由于所有数列长度都大于等于 Len,就能保证所有区间都能覆盖 0~Len-1,那么所得解即为 Len。
- #include#include const int maxn = 100005;
- int l,
- r,
- n,
- m;
- int minLen;
- int main() {
- scanf("%d%d", &n, &m);
- minLen = n;
- for (int i = 0; i < m; i++) {
- scanf("%d%d", &l, &r);
- minLen = std: :min(minLen, r - l + 1);
- }
- printf("%d\n", minLen);
- int cnt = 0;
- for (int i = 0; i) {
- printf("%d ", cnt);
- cnt++;
- cnt %= minLen;
- }
- printf("\n");
- return 0;
- }
--(完)--
思维 - CF-739A
来源: http://www.bubuko.com/infodetail-2118494.html