POJ 2823 单调队列+IO优化
传送门
在网上逛的时候,看到一个博主说里下单调队列,然后说这题是单调队列的直接应用.就做了下,发现单调队列其实也很容易嘛.不过这题在WS的POJ上需要加上IO优化,不然就一直TLE.或许是我的程序写措了.不可能吧^-^
具体的单调队列介绍还是请看这位博主的.单调队列保证队列的首元素是最优的,如果队首元素”已过期”就”出队”,在考虑新元素时,弹出队列中每当前这个元素优的所有元素,然后这个元素入队.一直这样操作,就能保证队首元素一直是最优的.下面给出IO优化的两个函数:
int get_int()
{
int ret=0
char c
char flag=0
c=getchar();
while(‘ ‘ == c || ‘\n’ == c)
c=getchar();
if(‘-‘ == c)
{
flag=1
c=getchar();
}
while(isdigit(c))
{
ret = ret*10+c-‘0’
c=getchar();
}
if(1==flag)
ret = -ret
return ret
}
void put_char(int n)
{
if(n>=10)
put_char(n/10);
putchar(n%10 + ‘0’);
}
