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 a 0,..., 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 0, a 1,..., a k-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<=10 6), the number of integers in the sequence. The second contains n integers a 0,..., 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
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#include #include #include #include using namespace std;const int MAXN = 1e6 + 100;int num[MAXN];int sum[MAXN];int q[MAXN];int main(){ int n; while(~scanf("%d", &n), n){ sum[0] = 0; for(int i = 1; i <= n; i++){ scanf("%d", num + i); sum[i] = sum[i - 1] + num[i]; } for(int i = n + 1; i <= 2*n; i++) sum[i] = sum[i - 1] + num[i - n]; // for(int i = 0; i <= 2*n; i++) // printf("%d ", sum[i]);puts(""); int head = 0, tail = -1, ans = 0; for(int i = 1; i <= 2 * 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] >= 0)ans++; while(head <= tail && q[head] <= i - n)head++; } printf("%d\n", ans); } return 0;}