-
枚举
-
前缀和，差分
前缀和：sum[ i ] = a[ i ] + sum[i - 1] 前 i 个数的求和。
差分：delta[ i ] = a[ i ] - a[ i -1 ] 第 i 个数 - 第 i-1 个数。
例题：https://ac.nowcoder.com/acm/problem/16649
1 #include<bits/stdc++.h> 2 using namespace std; 3 /** 4 对于区间问题，简化成区间端点的问题； 5 比如： 前缀和 或者 差分，利用端点既可以维护整个数组，降低时间复杂度 6 */ 7 int L,M,cnt; 8 int delta[10010]; //差分数组 9 10 int main() 11 { 12 cin>>L>>M; 13 while(M--) 14 { 15 int l,r; 16 scanf("%d%d",&l,&r); 17 if(l>r) swap(l, r); 18 delta[l]++; //更新差分数组的值 19 delta[r+1]--; 20 } 21 int a=0;//只需要单个的a就可以得到a[i]每一个位置的值，但我们不需要保存，只需要判断a[i]==0即可 22 for(int i=0;i<=L;i++) 23 { 24 a+=delta[i]; 25 if(a==0) 26 cnt++; 27 } 28 cout<<cnt; 29 return 0; 30 }