首页 > ACM题库 > HDU-杭电 > HDU 4193-Non-negative Partial Sums-数据结构-[解题报告]HOJ
2015
05-23

HDU 4193-Non-negative Partial Sums-数据结构-[解题报告]HOJ

Non-negative Partial Sums

问题描述 :

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?

输入:

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.

输出:

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.

样例输入:

3
2 2 1
3
-1 1 1
1
-1
0

样例输出:

3
2
0

/*
分析:
    数据结构的分析类问题。
    觉得是道挺有意思的水题,本来没想发,不过随便搜了下后发现清一色的单调队列。。
应该很快也要退役了,还是发下吧。。
    这里说的移动,都是将最后一个元素放到首位。
    1.如果sum<0,那么坑定ans=0;
    2.很容易发现一个性质,如果当前的长度为n的序列满足题中的那个条件,那么我们可以
只将最后一个元素移动到最前面;既将最后的元素放到首位,如果之前的序列满足条件,则
此次移动后得到的序列是否满足情况,全权由此元素决定(因为不考虑这次移动后的首元素,
其后的n-1个元素所组成的序列,一定满足题中条件):
    如果这个元素>=0,那么这次移动得到的新队列同样满足题中的条件;
    如果这个元素<0,那么可以设置一个量来累加这个值,直到某次移动移动后这个累计
值>=0,此时ans可以+1,并且要把这个累计值清零。
    再详细的看代码吧,很短。至于单调队列?啥东西囧~?估计也就我这种非计算机专业
的半吊子会这样搞吧。。还是赶紧抽段时间恶补计算机的东西吧。。。

转载。。请声明:——————–Ice_Crazy(见鬼,这玩意儿谁会转载。。)
    
                                                                     2013-07-31
*/

#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int N=1000006;

int n,num[N],ans;
int main()
{
    int i,l;
    int p,acc,sum,cnt;
    while(scanf("%d",&n),n)
    {
        sum=0;
        for(i=0;i<n;i++){scanf("%d",&num[i]);sum+=num[i];}
        if(sum<0)    {printf("0\n");continue;}

        p=n-1;
        ans=cnt=sum=0;
        while(cnt<=p)
        {
            sum+=num[cnt++];
            while(sum<0)    sum+=num[p--];
        }
        acc=0;
        while(p>=0)
        {
            if(acc>=0)        ans++;
            if(acc<0)        acc+=num[p];
            else if(num[p]<0)    acc=num[p];
            p--;
        }
        printf("%d\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/9697885