hdu 4193 单调队列

题意是给你n个数 组成的环 求以一个数开头 的数列所有前缀都为非负数的数列的个数：

思路： 先扩展成2*n的数列 然后求出sum【i】表示前i项的和 对每个i>.=n结尾的数列 只要单调队列里的最小值大于等于sum【i-n】就满足情况（想想为什么） 对于单调队列 只要维护长度大于等于n 递增的就行；

#include
  
   
#include
   
     #include
     
     using namespace std
     ; int num
     [2001000
     ],sum
     [2001000
     ],id
     [2001000
     ]; int main() { int n
     ,i
     ,j
     ; while(~scanf
     ("%d"
     ,&n
     ),n
     ) { for(i
     =1
     ;i
     <=n
     ;i
     ++) { scanf
     ("%d"
     ,&num
     [i
     ]); num
     [i
     +n
     ]=num
     [i
     ]; } sum
     [0
     ]=0
     ; for(i
     =1
     ;i
     <=n
     +n
     ;i
     ++) { sum
     [i
     ]=sum
     [i
     -1
     ]+num
     [i
     ]; } int front
     =0
     ,top
     =0
     ; int t
     =0
     ; for(i
     =1
     ;i
     <n
     +n
     ;i
     ++) { while(front
     <top
     &&sum
     [i
     ]<sum
     [id
     [top
     ]]) top
     --; id
     [++top
     ]=i
     ; if(i
     >=n
     &&sum
     [id
     [front
     +1
     ]]>=sum
     [i
     -n
     ]) t
     ++; while(id
     [top
     ]-id
     [front
     +1
     ]>=n
     ) front
     ++; } printf
     ("%d\n"
     ,t
     ); } return 0
     ; }