NAIVE-03

[文章目录]

1.单调队列

单调队列究竟有什么用呢?一直不明白。只不过是一个单调的队列吧
有一种问题就是在定区间找最大值或最小值;比如给你一个数列,有那么一个滑块,让你求每次移动一个单位的滑块,求滑块中框住的数中的最大值。

最简单的方法肯定是每次比较一遍,不过很显然,在滑块移动过程中,有很多次比较是重复的,所以引入了单调队列。主要思想就是既然我后面来了一个新的数比原来的大,那么好了,我可以抛弃原来的数了,因为再以后的任何一个区间都不会有只包含原数,而不包含新数的情况。如果不比原数大,那么我就把它留着,等到原数不在区间中时再使用。或者是又来了一个新人(%%%),没等退位,就把原数干掉了的同时把它也干掉了。

所以维护这个单调队列有两个步骤;
一:来了新人,干掉一片。
二:老元帅退位,皇冠送给老二。

代码如下:

while(head<=tail&&f[que[tail]]<=f[i-1])
        tail--;//长江后浪推前浪,干掉一片
que[++tail]=i-1;//成功进入上层,等待被干掉,或元老死亡继位
while(que[head]<i-m)
        head++;//元老死亡

(移动定区间,找min,max,都行)
还有一些更高级的单调队列的用法。。。总之多做题吧。

2.static

这个东西加在全局变量上,对于竞赛好像并没有什么用。

如果加在局部变量上:

1.这个变量和全局引用的初值一样,为0.

2.这个变量是在全局的内存里开的,不用担心栈空间。

3.这个变量只能在局部引用的函数内使用,并且“可持久化”,上一次改变变量的值,下一次调用函数变量的值为改变后的。

推荐篇blog:%%%%dalao

3.this指针

结构体函数中可以运用的指针。指向引用此函数的结构体。

好像一句话把该说的都说了。

原谅我太NAIVE

发表评论

邮箱地址不会被公开。 必填项已用*标注