算法参考第一篇 @是青白呀 的题解。

我用函数计算最大值，直接返回极差与返回最大值后计算极差的答案居然不一样？

/*
 * @Author: Michael Lee
 * @Date: 2022-03-12 11:41:15
 * @LastEditors: Michael Lee
 * @LastEditTime: 2022-03-12 22:25:21
 * @Description: fixed AT4143 [ARC098C] Range Minimum Queries
 */
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<assert.h>

using namespace std;
//支持负数
template<typename T>
inline void read(T &x)
{
    char ch;bool flag = 0;
    while(!isdigit(ch=getchar()))
        (ch=='-')&&(flag=true);
    for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');
    (flag)&&(x=-x);
}
template<typename T>
void print(T x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

typedef long long ll;
const int N=2e3+10;
int n,k,q,a[N],ans=0x3f3f3f3f;

inline int solve(int x)    //返回最小值x时的极差
{
    priority_queue<int,vector<int>,greater<int> > gq;//great q
    int l,r;
    for(l=1,r=1;l<=n&&r<=n;l=r)
    {
        while(l<=n&&a[l]<x)  l++;
        priority_queue<int,vector<int>,greater<int> > sq;//small q
        for(r=l;r<=n&&a[r]>=x;r++)
            sq.push(a[r]);
        while(sq.size()>=k)
            gq.push(sq.top()),sq.pop();
    }
    if(gq.size()<q) return 0x3f3f3f3f;
    for(int i=1;i<q;i++)    gq.pop();
    return gq.top()-x;
}
inline int solve2(int x)   //返回最小值x时的，删掉的最大值的最小值
{
    priority_queue<int,vector<int>,greater<int> > gq;//great q
    int l,r;
    for(l=1,r=1;l<=n&&r<=n;l=r)
    {
        while(l<=n&&a[l]<x)  l++;
        priority_queue<int,vector<int>,greater<int> > sq;//small q
        for(r=l;r<=n&&a[r]>=x;r++)
            sq.push(a[r]);
        while(sq.size()>=k)
            gq.push(sq.top()),sq.pop();
    }
    if(gq.size()<q) return 0x3f3f3f3f;
    for(int i=1;i<q;i++)    gq.pop();
    return gq.top();
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("D.in","r",stdin);
//	freopen(".out","w",stdout);
	#endif
    read(n),read(k),read(q);
    for(int i=1;i<=n;i++)   read(a[i]);

    ans=solve(0);
    for(int i=1;i<=n;i++)
        ans=min(ans,solve2(a[i])-a[i]);

    assert(solve(a[8])==(solve2(a[8])-a[8]));   //RE？

    print(ans),putchar('\n');
	return 0;
}

/*
hack:
11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784
*/