HDU 4193
题意：给n个数字组成的序列（n <= 10^6），求该序列的循环同构序列中，有多少个序列的任意前i项和均大于或等于0.
思路：
这题看到数据规模觉得只能用最多O（nlogn）的算法，然后想到了之前刚做过的有关最小表示法的题，但还没证明出一个做这题有效的算法出来。
后来看过题解，发现用的最多的方法是单调队列，，然而我对这个知识点知之甚少orz
/*科普君：from单调队列
单调队列是指：队列中元素之间的关系具有单调性，而且，队首和队尾都可以进行出队操作，只有队尾可以进行入队操作。
以单调不减队列为例：队列内的元素（e1，e2，e3…en）存在（e1<=e2<=e3<=…<=en）的关系，所以队首元素e1一定是最小的元素。与优先队列不同的是，当有一个新的元素e入队时，先要将队尾的所有大于e的元素弹出，以保证单调性，再让元素e入队尾。
例如这样一组数（1，3，2，1，5，6），进入单调不减队列的过程如下：
1入队，得到队列（1）；
3入队，得到队列（1，3）；
2入队，这时，队尾的的元素3>2，将3从队尾弹出，新的队尾元素1<2，不用弹出，将2入队，得到队列（1，2）；
1入队，2>1，将2从队尾弹出，得到队列（1，1）；
5入队，得到队列（1，1，5）；
6入队，得到队列（1，1，5，6）*/
利用单调队列的解题思路是：//参考：
首先用循环序列的一般处理方法，将数列复制并接在一起。
然后处理出来sum，sum[i]表示a[1]~a[i]的和。
设S[i]为长度为n的子序列前i项之和,假设子序列的最后一个数的下标为就j，那么j-n+1 <= i <= j，S[i] = A[j-n+1] + A[j-n] + … + A[i],.
Sum[i]和S[i]的转化关系为：当前子序列的末尾数的下标为j，S [i] =Sum[i] – Sum[j-n]。
题中要找满足所有S(i) >= 0条件的n长子序列，所以只需要找出最小的S(i)，如果它的值都大于等于0的话，该序列就满足条件，ans++即可。
使用单调递增队列来寻找最小的S[i]。
其他解题思路：//参考：
先考虑如果整个序列和sum<0，那么肯定ans=0；
再考虑一个性质，如果当前的长度为n的序列满足题中条件，那么我们可以只将最后的元素放到首位，如果移动前序列满足条件，则此次移动后得到的序列是否满足条件便由此元素决定。 如果这个元素 >= 0，那么这次移动得到的新队列同样满足题中的条件，ans++； 如果这个元素 < 0，则再次移动并累加移动元素值，直到某次移动后这个累计值 >= 0，此时ans可以+1，并且要把这个累计值清零。
当移动后序列又成为原合法序列时，结束移动。
code：（后一种解题思路）
/** @author Novicer* language : C++/C*/#include<iostream>#include<sstream>#include<fstream>#include<vector>#include<list>#include<deque>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>#include<cctype>#include<cmath>#include<ctime>#include<iomanip>using namespace std;const double eps(1e-8);typedef long long lint;const int maxn = 1000000 + 5;int a[maxn];int main(){int n;while(cin >> n && n){int cnt = 0;int total = 0;for(int i = 1 ; i <= n ; i++){scanf("%d",&a[i]);total += a[i];}if(total < 0){cout << 0 << endl;continue;}else{int l = 0;int pos = n;int ans = 0;int sum = 0;while(l <= pos){sum += a[l];l++;while(sum < 0){sum += a[pos];pos–;}}//cout << l << endl;//cout << pos << endl;int tmp = 0;while(pos >= 1){if(tmp >= 0) ans ++;if(tmp < 0)tmp += a[pos];else if(a[pos] < 0) tmp = a[pos];pos–;}cout << ans << endl;}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
战胜困难，走出困境，成功就会属于你。
