HDU Non-negative Partial Sums （单一队列）
HDU Non-negative Partial Sums （单调队列）
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
3 2 2 1 3 -1 1 1 1 -1 0
Sample Output
3 2 0
通过这个题才对单调队列有一点了解
题意：一个数列，每一次把第一个数放到尾部，判断这个数列对于任意的 i (1<=i<=n) 是否都满足 sum[i]>=0，如果满足ans++,求最大的ans
思路：先把串加倍，队列需要维护长度为n的序列中的最小值放在队首
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#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<tail&&sum[i]<sum[que[tail-1]])
tail--;
que[tail++]=i;
}
void outque(int i)
{
if(i-n>=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;
}