HDU Non-negative Partial Sums （单调队列） - c++编程基础

Problem Description You are given a sequence of n numbers a ₀,..., a _n-1. A cyclic shift by k positions (0<=k<=n-1) results in the following sequence: a _k a _k+1,..., a _n-1, a ₀, a ₁,..., a _k-1. How many of the n cyclic shifts satisfy the condition that the sum of the fi rst i numbers is greater than or equal to zero for all i with 1<=i<=n?
Input Each test case consists of two lines. The fi rst contains the number n (1<=n<=10 ⁶), the number of integers in the sequence. The second contains n integers a ₀,..., a _n-1(-1000<=a _i<=1000) representing the sequence of numbers. The input will finish with a line containing 0.
Output For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.
Sample Input

Sample Output

3
2
0

通过这个题才对单调队列有一点了解

题意：一个数列，每一次把第一个数放到尾部，判断这个数列对于任意的 i (1<=i<=n) 是否都满足 sum[i]>=0，如果满足ans++,求最大的ans

思路：先把串加倍，队列需要维护长度为n的序列中的最小值放在队首

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define eps 1e-8 typedef __int64 ll; #define fre(i,a,b) for(i = a; i < b; i++) #define free(i,a,b) for(i = a; i > =b;i--) #define mem(t, v) memset ((t) , v, sizeof(t)) #define ssf(n) scanf("%s", n) #define sf(n) scanf("%d", &n) #define sff(a,b) scanf("%d %d", &a, &b) #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) #define pf printf #define bug pf("Hi\n") using namespace std; #define INF 0x3f3f3f3f #define N 2000005 int sum[N],a[N],n; int que[N],tail,head; void inque(int i) { while(head
            
             =que[head]) head++; } int main() { int i,j; while(~sf(n),n) { fre(i,1,n+1) { sf(a[i]); sum[i]=sum[i-1]+a[i]; } fre(i,n+1,n*2+1) sum[i]=sum[i-1]+a[i-n]; tail=head=0; int ans=0; fre(i,1,n) inque(i); fre(i,n,n*2) { inque(i); outque(i); if(sum[que[head]]>=sum[i-n]) ans++; } pf("%d\n",ans); } return 0; }