程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU Non-negative Partial Sums （單調隊列）

HDU Non-negative Partial Sums （單調隊列）

編輯：C++入門知識

HDU Non-negative Partial Sums （單調隊列）

Problem Description You are given a sequence of n numbers a₀,..., 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₀, a₁,..., a_k-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<=10⁶), the number of integers in the sequence. The second contains n integers a₀,..., 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

Sample Output

3
2
0

通過這個題才對單調隊列有一點了解

題意：一個數列，每一次把第一個數放到尾部，判斷這個數列對於任意的 i (1<=i<=n) 是否都滿足 sum[i]>=0，如果滿足ans++,求最大的ans

思路：先把串加倍，隊列需要維護長度為n的序列中的最小值放在隊首

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include


#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=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;
}