题目链接：http://acm.fzu.edu.cn/problem.php?pid=1914
题意：
给出一个数列，如果它的前i(1<=i<=n)项和都是正的，那么这个数列是正的，问这个数列的这n种变换里，
A(0): a1,a2,…,an-1,an
A(1): a2,a3,…,an,a1
…
A(n-2): an-1,an,…,an-3,an-2
A(n-1): an,a1,…,an-2,an-1
问有多少个变换里，所以前缀和都是正整数。
思路：因为变换是a[n]后面接着a[1]所以我们把数组a接到后面(即a[n+1]=a[1]..a[n+n]=a[n])。然后求一个前缀和。然后对于求以a[i]为起点的变换。即a[i],a[i+1],a[i+2]...a[n]...a[i-1]。当该变换满足全部前缀和都为正时，即a[i],a[i]+a[i+1],...,a[i]+...a[i+n]都为正。但是如果对于每个变换都用O(n)时间去计算每一个前缀和会TLE，所以预处理出原始数列的前缀和。那么上面的前缀和就可以转换成sum[i]-sum[i-1], sum[i+1]-sum[i-1],..,sum[i+n]-sum[i-1]。然后对于题目求的所有前缀和都为正，即在所有前缀和的最小值为正即可。那么就可以用滑动窗口维护最小值。用单调队列实现。 注意STL的deque会TLE，所以自己手写了的双端队列。
#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<queue>
#include<math.h>
#include<time.h>
#include<vector>
#include<iostream>
#include<string>
using namespace std;
typedef long long int LL;
const int MAXN = 1e6 + ;
LL sum[MAXN];
struct Deque{
int head, tail;
int val[MAXN];
Deque(){ head = ; tail = -; }
void push_back(int x){ val[++tail] = x; }
void pop_back(){ tail--; }
void pop_front(){ head++; }
int front(){ return val[head]; }
int back(){ return val[tail]; }
bool empty(){ return tail < head; }
void clear(){ head = ; tail = -; }
}deq;
int main(){
//#ifdef kirito
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//#endif
// int start = clock();
int t, n, Ca = ; scanf("%d", &t);
while (t--){
scanf("%d", &n);
for (int i = ; i <= n; i++){
scanf("%lld", &sum[i]);
sum[i + n] = sum[i];
}
for (int i = ; i <= * n; i++){
sum[i] += sum[i - ];
}
int ans = ; LL tmpx = ; deq.clear();
for (int i = ; i < n; i++){
while (!deq.empty() && sum[deq.back()] > sum[i]){
deq.pop_back();
}
deq.push_back(i);
}
for (int i = n; i < * n; i++){
while (!deq.empty() && sum[deq.back()] > sum[i]){
deq.pop_back();
}
deq.push_back(i);
while (!deq.empty() && deq.front() <= i - n){
deq.pop_front();
}
if (sum[deq.front()] - sum[i - n] > ){
ans++;
}
}
printf("Case %d: %d\n", Ca++, ans);
}
//#ifdef LOCAL_TIME
// cout << "[Finished in " << clock() - start << " ms]" << endl;
//#endif
return ;
}