羊羊菌 @ 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