天哪!竟然没人用优先队列!
小金羊又来水题了...
优先队列中的大根堆帮助我们把时间复杂度降到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;
}