【选段排序——堆】

题目

分析

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10;

int w[N];
priority_queue<int, vector<int>, greater<int>> hp1; //最小堆
priority_queue<int, vector<int>> hp2; //最大堆

int main()
{
  int n, p, q;
  cin >> n >> p >> q;
  for(int i = 1; i <= n; i++) 
    cin >> w[i];
  
  for(int i = p; i <= q; i++)
    hp1.push(w[i]), hp2.push(w[i]);
  int ans = hp2.top() - hp1.top();

  for(int i = p-1; i; i--)
  {
    hp2.push(w[i]); //维护最大值
    if(!(w[i] <= hp1.top())) //若不是更小值，发生抢夺
    {
      hp1.pop(); //最小值被抢
      hp1.push(w[i]); //给了个较大值
    }
    ans = max(ans, hp2.top() - hp1.top());
  }

  while(hp1.size()) hp1.pop(); //清空堆
  while(hp2.size()) hp2.pop();
  for(int i = p; i <= n; i++)
  {
    hp1.push(w[i]); //维护最小值
    if(i <= q) hp2.push(w[i]); //堆未存完[p,q]区间值
    else if(!(w[i] >= hp2.top())) //若不是更大值，发生抢夺
    {
      hp2.pop(); //最大值被抢
      hp2.push(w[i]); //给了个较小值
    }
    ans = max(ans, hp2.top() - hp1.top());
  }

  cout << ans;
}