为什么堆会T两个点

P1440 求m区间内的最小值

xzjds @ 2023-07-27 12:12:16

代码短小精悍

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int n,m,a[N];
int read()
{
    int x=0;char c='a';bool f=false;
    while (c<'0'||c>'9') {c=getchar();if (c=='-') f=1;}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    if (f) x=x*-1;
    return x;
}

struct mmp
{
    int dis,id;
    bool operator <(const mmp &now)
    const{
        return dis>now.dis; 
    }   
}; 

priority_queue<mmp> q;

int main() 
{
    n=read();m=read();
    for (int i=1;i<=n;i++)
    a[i]=read();
    cout<<'0'<<endl;
    q.push((mmp){a[1],1});
    for (int i=2;i<=n;i++)
    {
        while (!q.empty()&&(q.top().id<i-m)) q.pop();
        cout<<q.top().dis<<endl;
        q.push((mmp){a[i],i});
    }
    return 0;
}

by 聊机 @ 2023-07-27 12:33:43

本来就不是堆啊,单调队列复杂度和堆复杂度差一个 log 哥


by gzxworld @ 2023-08-22 10:41:14

@xzjds 将

cout<<q.top().dis<<endl;

改为

cout<<q.top().dis<<'\n';

可以通过啊


by xzjds @ 2023-09-24 12:23:04

@gzxworld 靠真的


|