hdu 4193 Non-negative Partial Sums 单调队列。

时间：2023-03-08 23:29:43
hdu 4193 Non-negative Partial Sums 单调队列。

Non-negative Partial Sums

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

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
Sample Output
3
2
Source
Recommend
lcy   |   We have carefully selected several similar problems for you:  4190 4192 4187 4188 4189 
 /*

 题意：

 刚刚又一道hdu的题目；

 题意：10^6个数字，有10^6种形式。

 如  a b c d ,  b c d a ,  c d a b,  d a b c;

 统计在所以情况中如果满足任意前i数和都>=0 的个数。

 想了一下，思路有了。可以这样子。

 任意前i数和都满足>=0，那么最小的是不是也就满足了呢?

 肯定的。所以。题目可以转换为

 以i为开头，长度为n的前提下，求最小值。

 这样的话，只有q[head].sum - s[ i - n];

  */

 #include<iostream>

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 using namespace std;

 int a[];

 int s[];

 typedef struct

 {

     int num;

     int sum;

 }Queue;

 Queue tmp,q[];

 int main()

 {

     int n,i,len,Num,tom;

     int head,tail;

     while(scanf("%d",&n)>)

     {

         if(n==)break;

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

             scanf("%d",&a[i]);

             len=n*;

         for(i=n+;i<=len;i++)

             a[i]=a[i-n];

         for(s[]=,i=;i<=len;i++)

             s[i]=s[i-]+a[i];

         head=;tail= -; Num=; tom=;

         for(i=;i<=len;i++)

         {

             tmp.num=++Num;

             tmp.sum=s[i];

             while( head<=tail && q[tail].sum>tmp.sum ) tail --;

             q[++tail]=tmp;

             if( i>n )

             {

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

                 if( q[head].sum-s[i-n]>=) tom++;

             }

         }

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

     }

     return ;

 }

相关文章