OJ题号：洛谷1801
思路：建立一个大根堆、一个小根堆。大根堆维护前i小的元素，小根堆维护当前剩下的元素。
1 #include<cstdio> 2 #include<queue> 3 #include<functional> 4 #include<vector> 5 int main() { 6 int m,n; 7 scanf("%d%d",&m,&n); 8 int a[m],u[n+1]; 9 for(int i=0;i<m;i++) scanf("%d",&a[i]); 10 u[0]=0; 11 for(int i=1;i<=n;i++) scanf("%d",&u[i]); 12 std::priority_queue<int,std::vector<int>,std::less<int> > b; 13 std::priority_queue<int,std::vector<int>,std::greater<int> > s; 14 unsigned int p=0; 15 for(int i=1;i<=n;i++) { 16 p++; 17 while((b.size()<p)&&!s.empty()) { 18 b.push(s.top()); 19 s.pop(); 20 } 21 for(int j=u[i-1];j<u[i];j++) { 22 if(b.size()<p) { 23 b.push(a[j]); 24 } 25 else { 26 if(a[j]<b.top()) { 27 s.push(b.top()); 28 b.pop(); 29 b.push(a[j]); 30 } 31 else { 32 s.push(a[j]); 33 } 34 } 35 } 36 printf("%d ",b.top()); 37 } 38 return 0; 39 }