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指针
结构体函数中可以运用的指针。指向引用此函数的结构体。
好像一句话把该说的都说了。