题目链接：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#include #include #include #include #include #include #include #include #include using namespace std;typedef long long int LL;const int MAXN = 1e6 + 10;LL sum[MAXN];struct Deque{ int head, tail; int val[MAXN]; Deque(){ head = 0; tail = -1; } 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 = 0; tail = -1; }}deq;int main(){//#ifdef kirito// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);//#endif// int start = clock(); int t, n, Ca = 1; scanf("%d", &t); while (t--){ scanf("%d", &n); for (int i = 1; i <= n; i++){ scanf("%lld", &sum[i]); sum[i + n] = sum[i]; } for (int i = 2; i <= 2 * n; i++){ sum[i] += sum[i - 1]; } int ans = 0; LL tmpx = 0; deq.clear(); for (int i = 1; i < n; i++){ while (!deq.empty() && sum[deq.back()] > sum[i]){ deq.pop_back(); } deq.push_back(i); } for (int i = n; i < 2 * 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] > 0){ ans++; } } printf("Case %d: %d\n", Ca++, ans); }//#ifdef LOCAL_TIME// cout << "[Finished in " << clock() - start << " ms]" << endl;//#endif return 0;}