CSP-J 2019 第一轮 第 22 题：程序（二，贪心配对更新）：m 0时输出是否一定小于2n

题目

#include<cstdio>
using namespace std;
int n, m;
int a[100], b[100];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        a[i] = b[i] = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (a[x] < y && b[y] < x) {
            if (a[x] > 0)
                b[a[x]] = 0;
            if (b[y] > 0)
                a[b[y]] = 0;
            a[x] = y;
            b[y] = x;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0)
            ++ans;
        if (b[i] == 0)
            ++ans;
    }
    printf("%d", ans);
    return 0;
}

假设输入的 $n$ 和 $m$ 都是正整数，$x$ 和 $y$ 都是在 $[1,n]$ 的范围内的整数，完成下面的判断题和单选题：

当 $m>0$ 时，输出的值一定小于 $2n$。（）

选项

• A. 正确
• B. 错误

答案

A

题解

答案：A. 正确。

ans 统计的是 a[1..n] 和 b[1..n] 中 0 的总个数。

由于 \(m>0\)，程序至少读入一组 \((x,y)\)：

• 最初所有元素都是 0，而 \(x,y\ge1\)，所以第一次一定满足 a[x] < y && b[y] < x，执行后 a[x]=y>0、b[y]=x>0。
• 后续若条件不成立，数组保持不变；若条件成立，即使清除了旧配对，最后也会执行 a[x]=y、b[y]=x，建立一个新配对。

因此，数组中始终至少有 两个非零元素（a、b 中各一个），最终有 \[ \boxed{\text{ans}\le 2n-2<2n}. \]

注意：配对数量不一定一直增加，但已有配对之后，不会变成一个配对都没有。