15分求助
查看原帖
15分求助
481621
Zhang_Wenjie楼主2023/7/11 09:56
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, a[N], s[N], ans;
int q[N], h, t;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i ++) 
	{
		cin >> a[i];
		a[i+n] = a[i];
	}
	for (int i = 1; i <= (n << 1); i ++)
		s[i] = s[i-1] + a[i];	
	h = 1;
	t = 0;
	for (int i = 1; i <= n; i ++) // 将前 1~n 个数据预处理
	{
		while (t >= h && s[q[t]] >= s[i]) t --;
		q[++t] = i;
	}
	for (int i = 2; i <= n; i ++) //每次向后移动窗口维护最小值 2~n+1 至 n~2n-1
	{
		int j = i + n - 1;
		while (t >= h && s[q[t]] >= s[j]) t --;
		q[++t] = j;
		while (t >= h && q[h] < i) h ++;
		if (s[q[h]] - s[i-1] > 0) ans ++;
	}
	if (s[n]) ans ++; // 特判 1~n 
	cout << ans;
	
	return 0;
}
2023/7/11 09:56
加载中...