单调队列—— HDU 4193 Non-negative Partial Sums

Non-negative Partial Sums

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1357 Accepted Submission(s): 518

Problem Description

You are given a sequence of n numbers a0,..., an-1. A cyclic shift by k positions (0<=k<=n-1) results in the following sequence: ak ak+1,..., an-1, a0, a1,..., ak-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<=106), the number of integers in the sequence. The second contains n integers a0,..., an-1 (-1000<=ai<=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

2 2 1

-1 1 1

-1

Sample Output

思路：

以一个长度n为5的数串（-10,3,-1,5,4）为例，如下图：

为了简化操作，A[]和Sum[]的存储都从1开始，0下标位置的值都赋为0。

A[]存储数字串以及它的一份拷贝，图中绿色方框为原数据（下标为1~n），黄色方框为拷贝（下标为n~2*n）。那么这个数串的一个序列就是图中红色方框圈起来的n个数，这里称红色方框为滑动窗口。

Sum[]存储一段数字的和，Sum[i]表示，A[1]~A[i]的和。如上图中Sum[3] = -10 + 3 + -1 = -8。

这里设S(i)为：假设滑动窗口的最后一个数的下标为就j，那么j-n+1 <= i <= j，S(i) = A[j-n+1] + A[j-n] + … + A[i]。题中要找满足滑动窗口内所有S(i) >= 0条件的序列，所以只需要找出最小的S(i)，如果它的值都大于等于0的话，该序列就满足条件。使用单调递增队列来寻找最小的S(i)。

Sum[i]和S(i)的转化关系为：当前滑动窗口的末尾数的下标为j，S (i) =Sum[i] – Sum[j-n]。

代码：

  
#define MAXN 1000000  
  
int sum[2*MAXN+5];  //将长度为n的数串复制为两份存储在sum中，下标从1开始  
                    //然后，sum[i]存储数串的前i项和  
int n;              //数串的长度  
  
int mq[MAXN+5];     //单调递增队列，队列元素为sum数组的下标  
int front;          //队首指针  
int rear;           //队尾指针，指向队尾的下一个位置  
  
void InitMQ(void)  
{  
    front = rear = 0;  
}  
  
bool IsEmpty(void)  
{  
    return front == rear;  
}  
  
void Push(int i)  
{  
    while (!IsEmpty() && sum[mq[rear-1]] > sum[i])  
    {  
        rear--;  
    }  
    mq[rear++] = i;  
}  
  
int Front(void)  
{  
    return mq[front];  
}  
  
void Pop(void)  
{  
    front++;  
}  
  
int main(void)  
{  
    sum[0] = 0;  
    while (scanf("%d", &n) != EOF)  
    {  
        if (n == 0)  
        {  
            break;  
        }  
  
        int i;  
        for (i = 1; i <= n; i++) //输入数据，并复制为两份  
        {  
            scanf("%d", &sum[i]);  
            sum[i+n] = sum[i];  
        }  
  
        for (i = 2; i < n*2; i++)        //计算前i项和  
        {  
            sum[i] += sum[i-1];  
        }  
  
        InitMQ();  
        for (i = 1; i < n; i++)  
        {  
            Push(i);  
        }  
  
        int count = 0;  
        for (i = n; i < n*2; i++)  
        {  
            if (Front() + n - 1 < i) //弹出不在滑动窗口内的数据  
            {  
                Pop();  
            }  
            Push(i);  
            if (sum[Front()] - sum[i-n] >= 0)    //序列是否满足条件  
            {  
                count++;  
            }  
        }  
  
        printf("%d\n", count);  
    }  
    return 0;  
}  
  
/* 
5 
-3 2 -1 5 3 
*/

补充：软件开发 , C++ ,