题目描述
uim在公司里面当秘书，现在有n条消息要告知老板。每条消息有一个好坏度，这会影响老板的心情。告知完一条消息后，老板的心情等于之前老板的心情加上这条消息的好坏度。最开始老板的心情是0，一旦老板心情到了0以下就会勃然大怒，炒了uim的鱿鱼。
uim为了不被炒，知道了了这些消息（已经按时间的发生顺序进行了排列）的好坏度，希望研究如何不让老板发怒。
uim必须按照时间的发生顺序逐条将消息告知给老板。不过uim可以使用一种叫“倒叙”的手法，例如有n条消息，小a可以从k,k+1,k+2...n,1,2...k-1这种顺序通报。
他希望知道，有多少个k，从k开始通报到n然后从1通报到k-1可以让老板不发怒。
输入输出格式
输入格式：
第一行一个整数n(1 <= n <= 10^6)，表示有n个消息。
第二行n个整数，按时间顺序给出第i条消息的好坏度Ai(-1000 <= Ai <= 1000)
输出格式：
一行一个整数，表示可行的方案个数。
方法：：根据某巨佬的吞噬算法写的，以下为转载自 MARSHALBEN的博客
*****************************************************
基础思路
简单看来这就是一个环，选能走下来的位数和一直不小于0的数。。。样例和没有没区别。然而环，单调队列神马的都太复杂了，现在请参考吞噬算法——
产生随机数 7，1，-5，2，-3（n=5）
首先，从第一位开始扫到第一个负数-5，然后用-5 吃掉前一个数1 ，于是变成了7, -4 ,2，-3
看来，一个1 满足不了-5 的胃口，于是接着往下吃 3 ,2,-3 .
呃，-4 撑死了……那就接着往下揍，找到了-3 ，-3 吃了2 ，变成3，-1，再往前吃，就成了2，好了，只剩下正数了，于是输出正数的个数 1。
通俗解释
那么，通俗点说呢，首先找到-5，要想成立，-5前面的和必须比0大，于是-5必须在1后面。同理，7，1，-5这个顺序不能打乱。于是推到最后，就行了。
栈实现
这里是用栈来实现
另一种解释
然后另一组随机数据-3，5，1，2 怎么办？
依然很简单。先将a【1】与a【4】吞噬了（a【i】，a【n】） 然后n– 直到a【1】 再push
**********************************************************************************************
所以代码就这样了
/*竟然起名叫做吞噬算法，据说是烟台一中自创的*/ /*因为我们不能有小于0的值，所以我们在入栈时如果小于零，我们要向前吞噬，直到大于零*/ /*最后数一下栈中有几个数就行了*/ #include<cstdio> #include<algorithm> #define maxn 1000001 using namespace std; int stack[maxn]; int note[maxn]; int top=0; int read() { int now=0; int f=1; char c=getchar(); while(c>'9'||c<'0') { if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9') { now*=10; now+=c-'0'; c=getchar(); } return now*f; } int main() { int n=read(); for(int i=1;i<=n;i++) { note[i]=read(); } for(int i=1;i<=n;i++) { top++; stack[top]=note[i]; while(stack[top]<0&&top>1) { top--; stack[top]+=stack[top+1]; stack[top+1]=0; } while(stack[top]<0) { stack[top]+=note[n]; n--; if(n<i) { printf("0");/*全找完了还是小肯定没办法了*/ return 0; } } } printf("%d",top); return 0; }