AcWing每日一题--校门外的树

https://www.acwing.com/problem/content/424/

1、直接模拟

 1 #include<iostream>
 2 using namespace std;
 3 const int N=10010;
 4 bool a[N];
 5 int main(void){
 6     int l,m;
 7     cin>>l>>m;
 8     for(int i=0;i<m;i++){
 9         int left,right;
10         cin>>left>>right;
11         for(int j=left;j<=right;j++){
12             a[j]=true;
13         }
14     }
15     int res=0;
16     for(int i=0;i<=l;i++){
17         if(!a[i]){
18             res++;
19         }
20     }
21     cout<<res;
22     return 0;
23 }

2、差分思想

 1 #include<iostream>
 2 using namespace std;
 3 const int N=10010;
 4 int a[N];
 5 int main(void){
 6     int l,m;
 7     cin>>l>>m;
 8     for(int i=0;i<m;i++){
 9         int left,right;
10         cin>>left>>right;
11         a[left]+=1;
12         a[right+1]-=1;
13     }
14     int res=a[0]==0?1:0;
15     for(int i=1;i<=l;i++){
16         a[i]+=a[i-1];
17         if(a[i]==0)
18             res++;
19     }
20     cout<<res;
21     return 0;
22 }

3、区间合并

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 typedef pair<int,int> PII;
 5 PII a[110];
 6 int main(void){
 7     int l,m;
 8     cin>>l>>m;
 9     for(int i=0;i<m;i++){
10         cin>>a[i].first>>a[i].second;
11     }
12     sort(a,a+m);
13     int ed=0;
14     int res=0;
15     for(int i=0;i<m;i++){
16         int left=a[i].first,right=a[i].second;
17         if(left>ed){
18             res+=left-ed;
19         }
20         ed=max(ed,right+1);
21     }
22     if(ed<l){
23         res+=l-ed+1;
24     }
25     cout<<res;
26     return 0;
27 }