洛谷【P2629】好消息，坏消息

浅谈队列：https://www.cnblogs.com/AKMer/p/10314965.html

题目传送门：https://www.luogu.org/problemnew/show/P2629

对于这种环状的序列问题，我们可以破环成链，两倍延长数组即可。

所以，以(k)开头的方案就可以对应数组里([k,k+n-1])了。

然后，我们求出数组的前缀和，以(k)开头的方案不会惹怒老板那就相当于(max(sum_{pos}),(posin [k,k+n-1]))不会小于(sum_k)。

我们用单调队列动态维护区间最小值然后与(sum_k)比较更新答案即可。

时间复杂度：(O(n))

空间复杂度：(O(n))

代码如下：

#include <cstdio>
using namespace std;

const int maxn=1e6+5;

int n,head,tail,ans;
int a[maxn<<1],sum[maxn<<1],list[maxn<<1];

int read() {
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return x*f;
}

int main() {
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=a[i+n]=read();
	for(int i=1;i<=n<<1;i++)
		sum[i]=sum[i-1]+a[i];
	for(int i=1;i<n<<1;i++) {
		while(head!=tail&&sum[list[tail-1]]>sum[i])tail--;
		while(head!=tail&&list[head]<i-n)head++;list[tail++]=i;
		if(i>=n&&sum[list[head]]>=sum[i-n])ans++;
	}
	printf("%d
",ans);
	return 0;
}