线上OJ:
一本通:1931:[05NOIP普及组] 校门外的树 (opens in a new tab)
AcWing:422. 校门外的树 (opens in a new tab)
洛谷:P1047 [NOIP2005 普及组] 校门外的树 (opens in a new tab)
核心思想:
1、由于数据量不大,所以本题可以用暴力直接枚举。时间复杂度为:
解法一、暴力
#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;
}