差分模板题
终于有一道会做的了(小声)
代码如下 (时间复杂度:O(nlogn) 快排导致)
#pragma GCC optimize(2)//O2优化
#include<iostream>
#include<algorithm>
using namespace std;
int res[1000010];
int main()
{
int n,k;
cin>>n>>k;
int l,r;
while(k--)
{
cin>>l>>r;
res[l]++,res[r+1]--;
}
for(int i=1;i<=n;i++)res[i]+=res[i-1];
sort(res+1,res+1+n);
cout<<res[(n+1)/2]<<endl;
return 0;
}
可以用nth_element函数,O(n)的时间
这个是什么意思,如何使用?还没学过这个函数[笑哭]