2013-02-27 11:44:03Morris
[UVA][單調隊列] 12393 - Non-negative Partial Sums
Non-negative Partial Sums
| Non-negative Partial Sums |
You are given a sequence of n numbers
a0,..., an-1.
A cyclic shift by k positions (
0
kn - 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
1in?
Input
Each test case consists of two lines.
The first contains the number n (
1n106), the number of integers in the sequence.
The second contains n integers
a0,..., an-1 (
-1000ai1000) 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
先將 A[] 複製一段，將環狀展開。
如果將其數列改成 S[i] = sigma(A[k]) (1<= k <= i),
那麼要符合所需要的規定，代表固定區間長度 S[i, i+n-1] 的最小值 要大於等於 S[i]。
使用單調隊列去維護他的調查。
因此做一個嚴格遞增的單調隊列，不懂單調隊列可以上網查一下，通常用在 動態規劃 中。
#include <stdio.h>
#define maxN 1048576<<1
int S[maxN], Q[maxN];
inline int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
// using monotone queue (increasing)
int n, x, i, j;
while(scanf("%d", &n) == 1 && n) {
for(i = 0; i < n; i++) {
ReadInt(&x);
S[i+n] = S[i] = x;
}
int n2 = n<<1;
for(i = 1; i < n2; i++)
S[i] += S[i-1];
int head = 0, tail = 0, ans = 0;
for(i = 0; i < n2; i++) {
while(head < tail && S[Q[tail-1]] >= S[i])
tail--;
Q[tail++] = i;
if(i >= n && S[Q[head]] >= S[i-n])
ans++;
while(head < tail && Q[head] <= i-n)
head++;
}
printf("%d\n", ans);
}
return 0;
}