方法一
首先建立一个数组,将其初值全部设置为1表示在该位置上有树。然后输入多组区间,将其区间内的数组值修改为0表示树被移走。最后遍历数组,若数组值为1则表示树还在。本题要注意的是边界问题:int i = 0;i <= l;i++ 闭区间【0,l】
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N = 10010; int tree[N]; int l,m; int cnt; int main() { scanf("%d%d",&l,&m); //数组值为1表示有树 for (int i = 0;i <= l;i++) tree[i] = 1; while (m--) { int x1,x2; scanf("%d%d",&x1,&x2); //数组值为0表示树被移走 for (int j = x1;j <= x2;j++) tree[j] = 0; } for (int i = 0;i <= l;i++) if (tree[i] == 1) cnt += 1; printf("%d\n",cnt); return 0; }
方法二:差分
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 10010; int delta[N];//差分数组 int tree[N]; int l,m; int cnt; int main() { scanf("%d%d",&l,&m); //tree数组值为1表示当前位置有树,该语句可以省略 for (int i = 0;i <= l;i++) tree[i] = 1; //由于tree数组全为1,所以差分数组只有第0位为1,其余位置全为0 delta[0] = 1; while (m--) { int x,y; scanf("%d%d",&x,&y); //修改差分数组 delta[x]--; delta[y + 1]++; } //位置0需要单独特判 if (delta[0] > 0) cnt += 1; //对差分数组求和得原数组 for (int i = 1;i <= l;i++) { delta[i] += delta[i - 1]; if (delta[i] > 0) cnt += 1; } printf("%d",cnt); return 0; }