天哪!竟然没人用优先队列!

小金羊又来水题了...


优先队列中的大根堆帮助我们把时间复杂度降到O(n+logn)

首先我们先了解一下大根堆...

大根堆的性质:根节点比子节点大,

这意味着最上面的节点的值是最大的。

在STL模板库里面的优先队列也就是大、小根堆

有自我维护的功能,

利用这个性质,我们可以将其排序,

这个题要排的序是:不下降子序列的长度。


来吧,上代码:

#include <iostream>
#include <queue>
//是优先队列的STL库
using namespace std;
priority_queue<int>qwq;

这里打断一下,我要说明大小根堆的格式:(dalao请无视)

//默认(大根堆):
priority_queue<类型名>堆名;
//大根堆标准写法:
priority_queue<类型名,vector<类型名>,less<类型名> >堆名;
//小根堆标准写法:
priority_queue<类型名,vector<类型名>,greater<类型名> >堆名;
//类型支持pair<a,b>的类型(先比较a,后比较b),
//支持string类型字典序排列。
//注:两个>不能连起来,">>"是右移符!

继续:(主函数)

int main()
{
int n,input,former,count=1;
cin>>n;
cin>>former;
for (int i=1;i<n;i++)
{
cin>>input;
if (input>former){count++;former=input;}
//不下降,就count++,更新原先的值former
else{qwq.push(count);former=input;count=1;}
//下降了,count恢复初始值1,也要更新
}
qwq.push(count);//防止只有一天的毒瘤数据
cout<<qwq.top();//输出最长的天数
return 0;
}

秒杀枚举、暴力、数组等...

05-06 12:47