Hdu4193 Non-negative Partial Sums (单调队列)

客官°小女子只卖身不卖艺 2022-09-18 07:51 82阅读 0赞

题意：

给你一个n项的序列，每次可以把序列的首项移动到末尾，一共可以构成n种序列，问一共有多少种序列满足条件：序列的前i项和都大于等于0（i:1~n)。

思路：

遇到循环队列，很普遍的想法：用2倍的数组把数据再存一遍。

用sum数组预处理出前缀和,数据范围不会超int,这样sum中任意两项之差即为这一段的数字之和。

对于区间i-n+1 ~ i,(i>=n)如果该区间内最小的sum\[k\],(i-n+1<=k<=i)满足sum\[k\]-sum\[i-n\]>=0,那么该区间满足题意

问题转化为求滚动区间中的最小值，可用单调队列处理

换了一种单调队列的写法，可能这种更清晰

#include <cstdio>
    #include <cstring>
    
    const int N=2000005;
    
    int data[N],q[N],sum[N];
    int front,rear,ans,n;
    
    void In (int i)
    {//单调递增队列,保证队首最小
    	while (front<=rear && sum[q[rear]]>=sum[i])
    		rear--;
    	q[++rear]=i;
    }
    
    void Out (int i)
    {
    	if (q[front]<=i-n)//保证队列长度不超过n
    		front++;
    	if (sum[q[front]]-sum[i-n] >=0)
    		ans++;
    }
    
    int main ()
    {
    	while (scanf("%d",&n),n)
    	{
    		front=0;
    		rear=-1;
    		ans=0;
    		memset(sum,0,sizeof(sum));
    		int i;
    		for (i=1;i<=n;i++)
    		{
    			scanf("%d",&data[i]);
    			data[i+n]=data[i];
    		}
    		for (i=1;i<2*n;i++)
    			sum[i]+=sum[i-1]+data[i];
    		for (i=1;i<n;i++)
    			In (i);
    		for (i=n;i<2*n;i++)
    		{
    			In(i);
    			Out(i);
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，82人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu2430Beans（单调队列）

Mr. Pote's shop sells beans now. He has N bags of beans in his warehouse, and he has nu

Love The Way You Lie/ 2023年10月11日 09:33/ 0 赞/ 119 阅读

相关单调队列详解

刚学单调队列时，在网上各大博客找文章学，说实话，写得很杂，表示自己懵逼了些许，最后硬是啃出来了，所以我决定要写一篇能让大部分人都看懂的博客来。说单调队列，那我们就

秒速五厘米/ 2022年10月29日 07:39/ 0 赞/ 193 阅读

相关理解单调栈与单调队列

单调栈单调栈：栈内的元素按照某种方式排序下单调递增或单调递减，如果新入栈的元素破坏的单调性，就弹出栈内元素，直到满足单调性。单调栈分为单调递增栈和单调递减栈：

谁践踏了优雅/ 2022年10月08日 12:27/ 0 赞/ 244 阅读

相关 Hdu4193 Non-negative Partial Sums (单调队列)

题意：给你一个n项的序列，每次可以把序列的首项移动到末尾，一共可以构成n种序列，问一共有多少种序列满足条件：序列的前i项和都大于等于0（i:1~n)。思路：

客官°小女子只卖身不卖艺/ 2022年09月18日 07:51/ 0 赞/ 83 阅读

相关单调队列模板

include <bits/stdc++.h> using namespace std; define inf 0x3f3f3f3f

不念不忘少年蓝@/ 2022年08月30日 15:52/ 0 赞/ 198 阅读

相关 The partial sum problem

The partial sum problem 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述 One day,Tom’s gi

布满荆棘的人生/ 2022年08月07日 15:54/ 0 赞/ 17 阅读

相关单调队列

定义单调队列就是具有单调性质的队列，即单调递减或单调递增的队列。用途在长度为n的数组中，从1到n-m+1分别为起点的连续的m个区间长度中求出最大值或最小值

Bertha 。/ 2022年05月18日 10:42/ 0 赞/ 254 阅读

相关【6319 HDU】Problem A. Ascending Rating（单调队列）

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6319][http_acm.hdu.edu.cn_showproblem.ph

亦凉/ 2022年05月17日 08:12/ 0 赞/ 112 阅读

相关 Necklace 单调队列

Problem Description You are given a necklace consists of N beads linked as a circle. Ea

谁借莪１个温暖的怀抱￠/ 2022年01月05日 15:29/ 0 赞/ 253 阅读

相关 HDU -1506 Largest Rectangle in a Histogram【单调栈单调队列】题解

目录 1.题目 2.代码 1.题目 A histogram is a polygon composed of

心已赠人/ 2021年07月24日 14:37/ 0 赞/ 407 阅读