Non-negative Partial Sums（单调队列）

时间：2021-05-12 20:34:05

Non-negative Partial Sums

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2622    Accepted Submission(s): 860

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 first 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 first 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
3
2 2 1
3
-1 1 1
1
-1
0
 
Sample Output
3
2
0
题解：给n个数，a0,a1,...an，求ai,ai+1,...an,a1,a2,...ai-1这样的排列种数，使得所有的前k（1<=k<=n)个的和都大于等于0；

求前缀和，加倍序列。

要满足前k个和都>=0,只需最小值>=0,所以用单调队列维护一个最小的前缀和sum[i],(i>=j-n+1)，这样就保证了sum[j]-sum[i]最大，所以区间【j-n+1，i]最小。

维护一个单调队列代表终止位置的最小值从小到大；
代码：
#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAXN = 1e6 + ;

int num[MAXN];

int sum[MAXN];

int q[MAXN];

int main(){

    int n;

    while(~scanf("%d", &n), n){

        sum[] = ;

        for(int i = ; i <= n; i++){

            scanf("%d", num + i);

            sum[i] = sum[i - ] + num[i];

        }

        for(int i = n + ; i <= *n; i++)

            sum[i] = sum[i - ] + num[i - n];

       // for(int i = 0; i <= 2*n; i++)

       //     printf("%d ", sum[i]);puts("");

        int head = , tail = -, ans = ;

        for(int i = ; i <=  * n; i++){

            while(head <= tail && sum[i] < sum[q[tail]])tail--;

            q[++tail] = i;

          //  printf("i = %d %d %d\n", i, sum[q[head]], sum[i - n]);

            if(i > n && sum[q[head]] - sum[i - n] >= )ans++;

            while(head <= tail && q[head] <= i - n)head++;

        }

        printf("%d\n", ans);

    }

    return ;

}

相关文章