差分
a[i]表示第i个草堆干草的捆数
b[1]+b[2]+···+b[i]表示a[i],即a[i]为b[i]的前缀和
当要在[l,r]之间添加干草时
只需b[l]++, a[l],a[l+1]···,a[n]所有都加了1
所以还需要b[r+1]–, _ a[r+1],a[r+2],···,a[n]都减了1_
这样才保证了a[l]~a[r]所有都加了1
时间复杂度O(n)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000010;
int b[N];
void insert(int l,int r){
b[l]++;
b[r+1]--;
}
int main(){
int n,m;
cin>>n>>m;
while(m--){
int l,r;
scanf("%d%d",&l,&r);
insert(l,r);
}
for(int i=1;i<=n;i++) b[i]+=b[i-1];//这里直接求前缀和,直接让b[i]=a[i],所以就不用另外定义a[i]
sort(b+1,b+n+1);
cout<<b[n/2+1]<<endl;
return 0;
}