♐ CSP_J 组真题
2005年
2. 校门外的树

线上OJ:

一本通:1931:[05NOIP普及组] 校门外的树 (opens in a new tab)
AcWing:422. 校门外的树 (opens in a new tab)
洛谷:P1047 [NOIP2005 普及组] 校门外的树 (opens in a new tab)

核心思想:

1、由于数据量不大,所以本题可以用暴力直接枚举。时间复杂度为:O(LM)=O(106)O(LM)=O(10^6)

解法一、暴力
#include <bits/stdc++.h>
using namespace std;
 
const int N = 10005;
 
int l, m, ans;
bool a[N];
 
// 暴力 O(LM)=O(10^6)
int main()
{
    scanf("%d %d", &l, &m);
    for(int i = 0; i < m; i++)
    {
        int st, ed;
        scanf("%d %d", &st, &ed);
        if(st > ed)  swap(st, ed);  // 防止输入坐标倒序
        for(int j = st; j <= ed; j++)  a[j] = true;  // 区间范围内的不做检查,直接标为true
    }
 
    for(int i = 0; i <= l; i++)  // 检查 [0, L]的每一个点,为false的即剩下的树
        if(!a[i])  ans++;
 
    printf("%d\n", ans);
    return 0;
}