求解析为什么小根堆不能push一个结构体。

P1886 滑动窗口 /【模板】单调队列

羊羊菌 @ 2019-09-22 21:35:37

各位大佬:

这道题我已经用单调队列过了一遍。

突然想到用优先队列,但想法有了,代码出现问题。。。

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

const int N = 1000010;

int n, k;
struct Range
{
    int x, y;
    bool operator< (const Range &W)const
    {
        return x > W.x;
    }
}range[N];

void Min()//小根堆//求最小 
{
    priority_queue< Range > heap;

    for (int i = 1; i <= n; i ++)
    {
        heap.push(range[i]);
        while (!heap.empty() && heap.top().y <= i - k)
            heap.pop();
        if (i >= k) printf("%d ", &heap.top().x);
    }
}

int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &range[i].x);
        range[i].y = i;
    }

    Min();

    return 0;

}

by ZhuMingYang @ 2019-09-22 21:39:01

都这样了为什么不用

pair<int,int>

by 梧桐灯 @ 2019-09-22 21:51:25

@羊羊菌 输出时去掉那个&


by 142857cs @ 2019-09-22 21:51:34

printf加&。。。


by 01190220csl @ 2019-09-22 21:55:57

@羊羊菌 可以:定义为priority_queue<Range, vector<Range>, greater<Range> >,然后就直接用了


by ZhuMingYang @ 2019-09-22 22:03:37

@01190220csl 他重载了<所以那样写反而是大根堆


by 羊羊菌 @ 2019-09-22 22:05:10

谢谢各位大佬


by 羊羊菌 @ 2019-09-22 22:30:41

@光随影走 哦哦,收到。 原来又是我粗心大意了


by 羊羊菌 @ 2019-09-22 22:31:06

@142857cs 谢谢大佬


by 羊羊菌 @ 2019-09-22 22:33:38

感谢各位的帮忙,虽然最后成功实现了之前的想法,但优先队列还是差一个数据节点,只有90分emmmm

果然还是单调队列的线性结构比较快呢

下面是我的代码,在此谢谢各位大佬帮我共同完成的代码

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

const int N = 1000010;

int n, k;

struct Range
{
    int x, y;

    bool operator< (const Range &W) const
    {
        return x < W.x;
    }
    bool operator> (const Range &W) const
    {
        return x > W.x;
    }

}range[N];

void Min()//小根堆//求最小 
{

    priority_queue<Range, vector<Range>, greater<Range> > heap;//greater需要重载 > 

    for (int i = 1; i <= n; i ++)
    {
        heap.push(range[i]);
        while (!heap.empty() && heap.top().y <= i - k)
            heap.pop();
        if (i >= k) printf("%d ", heap.top().x);
    }
}

void Max()//大根堆//求最大 
{
    priority_queue<Range, vector<Range>, less<Range> > heap;//less需要重载 < 

    for (int i = 1; i <= n; i ++)
    {
        heap.push(range[i]);
        while (!heap.empty() && heap.top().y <= i - k)
            heap.pop();
        if (i >= k) printf("%d ", heap.top().x);
    }
}

int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &range[i].x);
        range[i].y = i;
    }

    Min();
    printf("\n");
    Max();

    return 0;

}

by Vocalise @ 2019-10-03 10:26:58

建议重载小于号用friend


|