程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU Non

HDU Non

編輯:關於C++

 

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



 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved