起因是博主看了这道题的题解没几个人用队列来做，所以自己wa了9发搓了一道题解，给大家讲一讲这道题
思路
环变线性 + 维护区间最小值。
1. 环转直线
把数组复制一遍：a[i+n]=a[i]。这样线性数组上从 l开始长为 n 的一段就覆盖了“从 l 出发绕环一周”的所有路径。
对起点 l=1… n，对应的终点是 r=l+n-1，最大会到 2n-1，所以你构建前缀和到了 2n-1 就够了。
2. 判定一个起点是否可行
对于一个起点 l，我们需要检查从 l 开始，连续走 n 个元素，到达 r = l + n – 1 的这段区间 [l, r]。
我们要求在整个路径上，从起点开始的任意一段前缀和都不能为负数。
3. 滑动窗口 + 单调队列维护区间最小值
当窗口右端点 i 从 1 往右滑时：
• 把当前 S(i) 入队，保持队列里对应的 S(.) 单调递增（尾部弹出更大的）。
• 当窗口长度达到 n（即 i >= n）后，窗口为 [l=i-n+1, r=i]。队头若在窗口外（队头索引 < l）就弹出。此时队头就是 [l,r] 上的最小 S 的位置。
• 检查 min S – S(l-1) >= 0 即可决定该起点是否计数。
#include<bits/stdc++.h>
using namespace std;
const int N = 10000010;
typedef long long LL;
LL a[N], sum[N];
typedef list<int>::iterator Iter;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
deque<int> dq;
int n, k = 0;
cin >> n;
//复制数组到 a[n + 1 ... 2n],把环拉直
for (int i = 1; i <= n; i ++ ){
cin >> a[i];
a[i + n] = a[i];
}
//前缀和sum[i] = sum[i - 1] + a[i], 做到2n-1即可
for (int i = 1; i <= 2 * n - 1; i ++ ) sum[i] = sum[i - 1] + a[i];
//单调队列维护当前窗口[1...i]内的最小sum
for (int i = 1; i <= 2 * n - 1; i ++ ){
while (!dq.empty() && sum[dq.back()] > sum[i]) dq.pop_back();
dq.push_back(i);
if (i >= n) {
int l = i - n + 1;//当前窗口
int r = i;
while (!dq.empty() && dq.front() < l) dq.pop_front();
LL mn = sum[dq.front()];//窗口内最小的s[i]
LL base = sum[l - 1];//s[l - 1]
if (mn - base >= 0) k ++;//满足条件则该起点有效
}
}
cout << k;
return 0;
}几个关键点
- 为什么要计算到 2n – 1
因为我们需要检查所有可能的起点 l（从 1 到 n），而每个起点对应的区间是 [l,\, l+n-1]。
当 l = n 时，终点就是 r = l+n-1 = 2n-1，所以只需要把前缀和计算到 2n-1 就足够覆盖所有长度为 n 的区间。
- 为什么比较最小值与 S(l-1)
我们要求从起点 l 出发的连续 n 个数中，任意前缀和都不能小于零。
公式是：
在(l,r)中min(S(i)-S(l-1))>=0
这意味着，只要这段区间的最小前缀和 S(i) 都不小于起点之前的前缀和 S(l-1)，就可以保证从 l 出发的整个过程不会出现负值。
因此，判断一个起点是否合法，只需要比较：
在(l,r)中min(S(i)>=S(i-1)
- 单调队列的作用
为了高效地找到每个窗口 [l,r] 的 最小前缀和，我们用一个单调递增队列来维护候选下标：
• 队列中存的是下标，而不是值；
• 队列内对应的 S(.) 值严格递增；
• 这样，队头位置就永远是当前窗口内最小的前缀和所在的位置。
当窗口右端点向右移动时：
• 如果新加入的前缀和比队尾大，就直接入队；
• 如果新前缀和比队尾小，就把队尾弹出，保持单调递增；
• 如果队头已经滑出窗口，就把队头弹出。