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
0
 
Sample Output
3
2
0
 
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 ;
}

最新文章

  1. UIView的layoutSubviews和drawRect方法何时调用
  2. Mybatis关联查询和数据库不一致问题分析与解决
  3. android事件处理之基于监听
  4. C++小项目:directx11图形程序(四):d3dclass
  5. i2c总线,设备,驱动之间的关系
  6. ASP.NET Core 开发-Entity Framework (EF) Core 1.0 Database First
  7. [转]Android 延迟执行
  8. Android开发-API指南-&lt;compatible-screens&gt;
  9. nginx实现域名重定向
  10. UVA 11374 Airport Express(枚举+最短路)
  11. python的str,unicode对象的encode和decode方法
  12. Apache Spark 2.2.0 中文文档 - Spark SQL, DataFrames and Datasets Guide | ApacheCN
  13. 学习Git的最佳资料
  14. 微信小程序demo-环球小镇
  15. 使用Sublime Text 或 vs2017开发Node.js程序
  16. 第四节:Task的启动的四种方式以及Task、TaskFactory的线程等待和线程延续的解决方案
  17. 图论分支-Tarjan初步-割点和割边
  18. 【Python58--正则2】
  19. caller
  20. 黄聪:C# webBrowser控件禁用alert,confirm之类的弹窗解决方案

热门文章

  1. lamp-linux2
  2. Elasticsearch(八)【NEST高级客户端--Mapping映射】
  3. Elasticsearch(八)【NEST高级客户端--分析器】
  4. HTML5基础实例(三)
  5. 总结day26 ----验证客户端的合法性,已经操作系统,进程的简单初识别
  6. P1273 有线电视网(树形dp)
  7. power designer和uml应用
  8. leetcode-54-螺旋矩阵
  9. 使用nginx+uwsgi+Django环境部署
  10. windows 下 pyinstaller distutils not included with latest virtualenv (16.4.0)