HDU 4193 Non-negative Partial Sums（前缀和非负点个数，单调队列）_综合

题目链接：
HDU 4193 Non-negative Partial Sums
题意：
给一个 $n$ 个数的数环，求任意前缀和非负的点个数？
数据范围: $n\leq 10^6$
分析：
其实这道题和UVALive 6087 Fuel Stops是一样的。之前的做法也能做。
如果用单调队列做的话，需要转化成前缀和问题。对于位置 $i$ 的数，如果以它为结尾最长长度为 $n$ 的前缀和均非负，其实就是在求在它之前区间长度为 $n$ 的前缀和最小值，比较 $sum[min]和sum[n-i]$ 即可。维护一个单调递增队列。
时间复杂度： $O(n)$

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <climits>
using namespace std;
typedef long long ll;
const int MAX_N = 1000010 * 2;int n, head, tail;
int data[MAX_N], sum[MAX_N], que[MAX_N];int main()
{while (~scanf("%d", &n) && n) {for (int i = 1; i <= n; ++i) {scanf("%d", &data[i]);data[n + i] = data[i];}sum[0] = 0;for (int i = 1; i <= n * 2; ++i) {sum[i] = sum[i - 1] + data[i];}head = tail = 0;// 维护单调递增队列for (int i = 1; i <= n; ++i) {while (head != tail && sum[que[tail - 1]] >= sum[i]) {--tail;}que[tail++] = i;}int ans = 0;for (int i = n + 1; i <= 2 * n; ++i) {while (head != tail && i - que[head] >= n) {++head;}while (head != tail && sum[que[tail - 1]] >= sum[i]) {--tail;}que[tail++] = i;if (sum[que[head]] - sum[i - n] >= 0) ans++;}   printf ("%d\n", ans);}return 0;
}