學(xué)到了一個新的STL：nth_element
位于頭文件algorithm中亮曹，這個相當(dāng)于是算法課本第二章的線性時間選擇笆包，在線性時間內(nèi)選擇出第k大/小個元素坞生，非常的簡單
主要的原理是把第k個位置的交換一下坤候，所以最后輸出就好
用法
// 選出第k個元素
nth_element(arr+1,arr+k,arr+n+1);
nth_element(arr.begin(),arr.begin()+k,arr.end(),cmp);
// 輸出結(jié)果
cout<<arr[k];
開始解題
這個題目運用到了差分的知識點，模板題
前綴和
如果想求數(shù)組之間的和间护，可以引入一個數(shù)組
表示的是
的值亦渗，即
就可以將問題轉(zhuǎn)換為
差分
長度為 的整數(shù)序列，
個操作汁尺，每個操作包含三個整數(shù)
法精，表示將序列中
之間的每個數(shù)加上
。輸出進行完所有操作后的序列痴突。
解法：給區(qū)間中的每個數(shù)加上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
