学到了一个新的STL：nth_element
位于头文件algorithm中，这个相当于是算法课本第二章的线性时间选择，在线性时间内选择出第k大/小个元素，非常的简单
主要的原理是把第k个位置的交换一下，所以最后输出就好
用法
// 选出第k个元素
nth_element(arr+1,arr+k,arr+n+1);
nth_element(arr.begin(),arr.begin()+k,arr.end(),cmp);
// 输出结果
cout<<arr[k];
开始解题
这个题目运用到了差分的知识点，模板题
前缀和
如果想求数组之间的和，可以引入一个数组
表示的是
的值，即
就可以将问题转换为
差分
长度为 的整数序列，
个操作，每个操作包含三个整数
，表示将序列中
之间的每个数加上
。输出进行完所有操作后的序列。
解法：给区间中的每个数加上c：
#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,c;
int arr[100005];
int ed[100005];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&arr[i]);
ed[i]=arr[i]-arr[i-1];
}
while(m--){
scanf("%d%d%d",&l,&r,&c);
ed[l]+=c;
ed[r+1]-=c;
}
for(int i=1;i<=n;i++){
ed[i]+=ed[i-1];
cout<<ed[i]<<" ";
}
return 0;
}
本题解法
所以就只需要计算套用差分模板
#include<iostream>
#include<algorithm>
using namespace std;
int N,K,A,B;
int arr[1000005];
int main(){
cin>>N>>K;
for(int i=1;i<=K;i++){
cin>>A>>B;
arr[A]++;
arr[B+1]--;
}
for(int i=1;i<=N;i++){
arr[i]+=arr[i-1];
}
nth_element(arr+1,arr+(N+1)/2,arr+N+1);
cout<<arr[(N+1)/2];
return 0;
}
image.png
