c/c++语言开发共享栈与队列(含单调栈与单调队列)

栈 算法思路 栈((stack))又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元 …


算法思路

栈((stack))又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。 —-摘自 百度百科

栈与队列(含单调栈与单调队列)

由上述资料可知,栈是一个“先进后出”的数据结构。是只能在栈顶插入和删除的数据结构。如图,支持进栈((push))和出栈((pop))两种操作。由于只能从一端进栈,一端出栈,所以任一元素,如上图中的(s_2),必须得在比它后进栈的(s_3sim s_n)(s_n)(s_{top}))都出栈以后才能出栈,换句话说,先进来的元素必须等后进来的元素都出栈后才能出栈,故栈被称为“先进后出((filo))表”。

代码片段

进栈

进栈很简单,只需要将栈顶上移一格,然后在新的一格中放入元素即可。
栈与队列(含单调栈与单调队列)

void push(int x){   s[++top]=x; } 

出栈

出栈也很简单,只需要将栈顶下移一格即可,且不需要替换,因为如果有元素进栈需占用此格时会将它替换。
栈与队列(含单调栈与单调队列)

void pop(){   top--; } 

例题

p1739 表达式括号匹配

大意

给定一个以(@)结尾的表达式,判断其括号(只有“(”和“)”)是否匹配。
“(()())”,“((()))”匹配,但是“())”,“)()(”不匹配。

思路

如果只判断左右括号的数量的话显然是不行的,因为有很多数据显然过不去,如“)()(”,“())(()”等。
所以,这时候,我们就要使用栈了。逐个读入表达式,若为“(”则入栈(显然此时栈应该为(char)类型),若为“)”则判断,若栈顶为空或为“)”,即不为“(”,说明此时这个右半圆括号没有匹配到左半圆括号,说明不匹配。另外,若最后栈顶不为(0),说明还有剩下的括号没被匹配,也是不合法的。

代码
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char a[260],s[260]; int top=0; int main(){ 	cin>>a; 	for(int i=0;i<strlen(a);i++){ 		if(a[i]=='('){ 			s[++top]=a[i]; 		}else if(a[i]==')'){ 			if(a[i]==')'&&s[top]=='('){ 				top--; 			}else{ 				cout<<"no"; 				return 0; 			} 		} 	} 	if(top==0){ 		cout<<"yes"; 	}else{ 		cout<<"no"; 	} 	return 0; } 

p1449 后缀表达式求值

科普

逆波兰式((reverse polish notation)(rpn),或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)。
一个表达式(e)的后缀形式可以如下定义:
(1)如果(e)是一个变量或常量,则e的后缀式是(e)本身。
(2)如果(e)(e1 op e2)形式的表达式,这里(op)是任何二元操作符,则e的后缀式为(e1’e2′ op),这里(e1′)(e2′)分别为(e1)(e2)的后缀式。
(3)如果(e)((e1))形式的表达式,则(e1)的后缀式就是(e)的后缀式。
如:我们平时写(a+b),这是中缀表达式,写成后缀表达式就是:(ab+)
((a+b)*c-(a+b)/e)的后缀表达式为:
((a+b)*c-(a+b)/e)
(((a+b)*c)((a+b)/e)-)
(((a+b)c*)((a+b)e/)-)
((ab+c*)(ab+e/)-)
(ab+c*ab+e/-)

这里用树解释上述样例:
首先我们构建上述表达式的树,使得树的中序遍历为表达式(因为我们写的是中缀表达式。若想将前缀表达式,即波兰式 变为树,则需构建树让其前序遍历为表达式即可),那么,这棵树的后序遍历就是逆波兰式。
栈与队列(含单调栈与单调队列)

大意

给出后缀表达式,输出其值。

思路

一个个读入后缀表达式,遇到数字进栈,遇到符号计算栈顶和栈顶后一位的元素,最后输出栈顶即可。

代码
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int s[260],top=1; char x; int main(){ 	while(x!='@'){ 		x=getchar(); 		if(x=='.'){ 			top++; 		}else{ 			if(x>='0'&&x<='9'){ 				s[top]=s[top]*10+(x-'0'); 			} 			if(x=='+'){ 				top--; 				s[top-1]+=s[top]; 				s[top]=0; 			}else if(x=='-'){ 				top--; 				s[top-1]-=s[top]; 				s[top]=0; 			}else if(x=='*'){ 				top--; 				s[top-1]*=s[top]; 				s[top]=0; 			}else if(x=='/'){ 				top--; 				s[top-1]/=s[top]; 				s[top]=0; 			}else if(x=='@'){ 				break; 			} 		} 	} 	cout<<s[--top]; 	return 0; } 

队列

算法思路

栈是一端进和出的数据结构,对应地,队列是一端进、另一端出的数据结构。

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。 ——摘自 百度百科

栈与队列(含单调栈与单调队列)
与栈类似,不多赘述。

单调栈

算法思路

顾名思义,单调栈是一种栈内元素具有单调性的栈。也就是说,我们将数列内的元素入栈,且要让栈内元素单调递增或单调递减。维护这样一个栈也很简单(以下假设维护单调递增的单调栈),我们将栈内的元素(s_i)表示为数列(a)中的元素的下标,也就是说,当你在看到栈内有一个元素(x)时,它表示的不是数字(x),而是表示(a)数组中的元素(a_x),这一点需要特别注意。入栈时,如果栈顶元素表示的值大于加入的值(即(a_{s_{top}}>a_x)(x)表示加入的元素,显然为(a)数组中的元素下标),那么将(top–),即把栈顶踢出去。因为加进来的(x),即代表的(a_x),已经小于栈顶了,而我们要维护单调递增的栈,所以若(x)直接加入会破坏单调性,故要让栈顶出栈。等到所有的要踢出栈顶(top)都被踢出后(即现在的栈顶(top)符合(a_{s_{top}}<a_x)),就可以将(x)入栈了。
那么,单调栈有什么作用呢?显然,你可以维护一个单调递增的栈,通过按顺序一个个入栈序列中的元素,可以求出长度为(n)的序列(a)中的前(k)个元素的最小值((0<kle n))。因为栈是单调递增的,所以按顺序加入前(k)个元素后,栈顶一定是前(k)个数中的最小值。但是,你显然可以不用单调栈来解决这一个非常基础的问题。单调栈的主要作用之一就是求出序列中每个数右(或左)边第一个比它大(或者小)的数(详情请见例题1)。

例题

p5788 【模板】单调栈 & p2947 [usaco09mar]look up s

大意

求出序列中每个数右边第一个比它大的数。

思路

维护一个单调递减的栈,那么,对于每一个元素,让它被踢出去的那个元素一定是第一个比它大的元素。(建议自己画图好好分析一下)。

代码
#include<iostream> #include<cstdio> #define maxn 100005 using namespace std; int n,a[maxn]; int s[maxn],top=0; int ans[maxn]; void push(int x){ 	while(a[s[top]]<a[x]&&top>0){ 		ans[s[top]]=x; 		top--; 	} 	s[++top]=x; } int main(){ 	scanf("%d",&n); 	for(int i=1;i<=n;i++){ 		scanf("%d",&a[i]); 	} 	s[++top]=1; 	for(int i=2;i<=n;i++){ 		push(i); 	} 	for(int i=1;i<=n;i++){ 		printf("%d ",ans[i]); 	} 	return 0; } 

p1901 发射站

大意

(n)个发射站,每一个发射站有一个高度(h_i)和能量值(v_i),对于每个发射站(i),它左边和右边第一个比它高的发射站都可以接收到它发出的信号(即累计值加上(v_i)),求每个信号塔累计的能量值总和的最大值。

思路

同上两题,只不过要加两次。

代码
#include<iostream> #include<cstdio> #include<cstring> #define maxn 1000005 using namespace std; int n,a[maxn],v[maxn]; int s[maxn],top=0; int ans[maxn]; void push(int x){ 	while(a[s[top]]<a[x]&&top>0){ 		ans[x]+=v[s[top]]; 		top--; 	} 	s[++top]=x; } int main(){ 	scanf("%d",&n); 	for(int i=1;i<=n;i++){ 		scanf("%d%d",&a[i],&v[i]); 	} 	s[++top]=1; 	for(int i=2;i<=n;i++){ 		push(i); 	} 	memset(s,0,sizeof(s)); 	top=0; 	s[++top]=n; 	for(int i=n-1;i>=1;i--){ 		push(i); 	} 	int mmax=-1; 	for(int i=1;i<=n;i++){ 		mmax=max(mmax,ans[i]); 	} 	printf("%d ",mmax); 	return 0; } 

p2422 良好的感觉

大意

有一长为(n)的序列(a),定义某区间([l,r])的值(comfort_{l,r} = minlimits_{i=l}^{r}{a_i} times sumlimits_{i=l}^{r}{a_i}),求(max(comfort_{i,j})(0 < ile jle n))

思路

可以想象,枚举每个区间需要耗费大量的时间,这很可能会使我们(tle)。我们不妨枚举(min(i,j)),显然我们只需要枚举(n)次,因为我们可以从(1)(n)枚举(i),计算以(a_i)为最小值的区间中的最大(comfort_{l,r}),因为(a_i ge 1),所以我们只要让区间越大越好,所以我们需要枚举的区间即为从(a_i)开始,左右两边各延伸到离它最近的比它小的两个位置(不包括这两个比它小的值)(因为这样就可以保证区间内没有小于(a_i)的数,即(a_i)为区间内最小值,且区间最大),计算所有的(a_i)计算的区间的和乘(a_i)(即以(a_i)为最小值的最大(comfort)值)的最大值即为所求最大值。

代码
#include<iostream> #include<cstdio> #include<cstring> #define maxn 100005 using namespace std; int n,a[maxn]; long long pre[maxn]; int le[maxn],ri[maxn]; int s[maxn],top=0; void pushr(int x){ 	while(a[s[top]]>a[x]&&top>=0){ 		ri[s[top]]=x; 		top--; 	} 	s[++top]=x; } void pushl(int x){ 	while(a[s[top]]>a[x]&&top>=0){ 		le[s[top]]=x; 		top--; 	} 	s[++top]=x; } int main(){ 	scanf("%d",&n); 	for(int i=1;i<=n;i++){ 		scanf("%d",&a[i]); 		pre[i]=pre[i-1]+a[i]; 	} 	s[++top]=1; 	for(int i=2;i<=n;i++){ 		pushr(i); 	} 	memset(s,0,sizeof(s)); 	top=0; 	s[++top]=n; 	for(int i=n-1;i>=1;i--){ 		pushl(i); 	} 	for(int i=1;i<=n;i++){ 		ri[i]=ri[i]==0?n+1:ri[i]; 	} 	long long ans=-1; 	for(int i=1;i<=n;i++){ 		ans=max(ans,(long long)(a[i]*(pre[ri[i]-1]-pre[le[i]]))); 	} 	printf("%lld",ans); 	return 0; } 

单调队列

算法思路

我们刚才讲到,单调栈可以算出一组数据中前(k)个数据中的最值(虽然不用单调栈更简单易懂),那么,如何计算一组数据中任意连续(k)个数据的最值呢((0<kle n))?这时,我们就要用到单调队列了(注:用线段树也可以)。
单调队列相当于单调栈,但是它在队头也可以进行删除操作(即(head++))。以上述题目(即例题(1))为例,我们只要控制这个单调队列的队头始终满足在所求范围内即可。更详细的思路见例题(1)

例题

p1886 滑动窗口 /【模板】单调队列

大意

有一串长(n)的序列,有一个长(m)的窗口从(1)(n-m+1)滑动((0<m<=n)),求每滑动一次窗口的最值。

思路

模板题。
维护队列(q)(当然能用(stl)),(这里讲最大值的做法,最小值同理)每次加入一个元素,从队尾把小于此元素的从队尾出队(因为当前的元素已经比它大了,且窗口向右滑动,所以它必定不可能再一次成为最大值),从队首将不在范围内的元素从队首出队,这时队首即为最大值。
代码中,先将前(k-1)个元素入队,然后循环(i)(kle ile n)),枚举队尾,用(push)函数从队尾插入,同时从队头删去(i-k+1)之前的元素,即已经不在滑动窗口内的元素,输出队头。

代码
#include<iostream> #include<cstdio> #define maxn 1000005 using namespace std; int n,k; int a[maxn]; int q1[maxn],q2[maxn],h1=1,t1=0,h2=1,t2=0;//q1维护最大值,q2维护最小值  int ans1[maxn],ans2[maxn]; void push1(int x,int l){ 	while(t1>=h1&&a[x]>a[q1[t1]]){ 		t1--; 	} 	q1[++t1]=x; 	while(t1>=h1&&q1[h1]<l){ 		h1++; 	} } void push2(int x,int l){ 	while(t2>=h2&&a[x]<a[q2[t2]]){ 		t2--; 	} 	q2[++t2]=x; 	while(t2>=h2&&q2[h2]<l){ 		h2++; 	} } int main(){ 	scanf("%d%d",&n,&k); 	for(int i=1;i<=n;i++){ 		scanf("%d",&a[i]); 	} 	q1[++t1]=1; 	q2[++t2]=1; 	for(int i=2;i<=k;i++){ 		push1(i,-1); 		push2(i,-1); 	} 	ans1[1]=q1[h1]; 	ans2[1]=q2[h2]; 	for(int i=k+1;i<=n;i++){ 		push1(i,i-k+1); 		push2(i,i-k+1); 		ans1[i-k+1]=q1[h1]; 		ans2[i-k+1]=q2[h2]; 	} 	for(int i=1;i<=n-k+1;i++){ 		printf("%d ",a[ans2[i]]); 	} 	printf("n"); 	for(int i=1;i<=n-k+1;i++){ 		printf("%d ",a[ans1[i]]); 	} 	return 0; } 

双倍经验(只需求最大值):p2032 扫描

p2629 好消息,坏消息

大意

给定一个环,问从任意元素开始累加,有多少种情况使得累加时总和(tot)恒大于等于(0)

思路

断环成链,维护单调队列和前缀和(pre_i),若某一长度为(n)的序列(isim i+n-1)的最小值减(pre_{i-1})大于零的话即可行。

代码
#include<iostream> #include<cstdio> #define maxn 1000005 using namespace std; int n,k; int a[maxn*2],pre[maxn*2]; int q[maxn],h=1,t=0; int ans[maxn]; void push(int x,int l){ 	while(t>=h&&pre[x]<pre[q[t]]){ 		t--; 	} 	q[++t]=x; 	while(t>=h&&q[h]<l){ 		h++; 	} } int main(){ 	scanf("%d",&n); 	k=n; 	n*=2; 	for(int i=1;i<=k;i++){ 		scanf("%d",&a[i]); 		a[i+k]=a[i]; 	} 	for(int i=1;i<=n;i++){ 		pre[i]=pre[i-1]+a[i]; 	} 	q[++t]=1; 	for(int i=2;i<=k;i++){ 		push(i,-1); 	} 	ans[1]=q[h]; 	for(int i=k+1;i<n;i++){ 		push(i,i-k+1); 		ans[i-k+1]=q[h]; 	} 	int tot=0; 	for(int i=1;i<=n-k;i++){ 		if(pre[ans[i]]-pre[i-1]>=0){ 			tot++; 		} 	} 	printf("%d",tot); 	return 0; } 

单调队列优化dp

例题

p1725 琪露诺

大意

有一串长度为(n+1)的序列(a),从(0)出发,在某个节点(i)能走到(i+lsim i+r)的任意位置,(tot)累加当前位置的(a_i),求离开时的最大(tot)值((i+r>n)代表从(i)节点能离开)。

思路

显然此题暴力代码复杂度为(o(n^2))(f_i=maxlimits_{j=max(0,i-r)}^{i-l}{f_j}(l<=i<=n)),那么,我们只要开一个单调队列求前文的(max(f_j))即可。

代码

(细节很多)

#include<iostream> #include<cstdio> #include<cstring> #define maxn 1000005 #define inf 0x3f using namespace std; int n,l,r; int a[maxn]; int q[maxn],h=1,t=0,maxx[maxn]; int f[maxn]; void push(int x,int l){ 	while(f[x]>f[q[t]]&&h<=t){ 		t--; 	} 	while(q[h]<l&&h<=t){ 		h++; 	} 	q[++t]=x; } void clear(int l){ 	while(q[h]<l&&h<=t){ 		h++; 	} } int main(){ 	scanf("%d%d%d",&n,&l,&r); 	memset(f,0x80,sizeof(f)); 	memset(q,-1,sizeof(q)); 	for(int i=0;i<=n;i++){ 		scanf("%d",&a[i]); 	} 	f[0]=0; 	push(0,-1); 	for(int i=l;i<=n;i++){ 		if(i-l>=l){ 			push(i-l,max(0,i-r)); 		}else{ 			clear(max(0,i-r)); 		} 		if(q[h]==-1){ 			f[i]=f[maxn-1]+a[i]; 		}else{ 			f[i]=f[q[h]]+a[i]; 		} //		for(int j=i-l;j>=max(0,i-r);j--){ //			f[i]=max(f[i],f[j]+a[i]); //		} 	} 	int ans=-inf; 	for(int i=n;i>=n-r+1;i--){ 		ans=max(ans,f[i]); 	} 	printf("%d",ans); 	return 0; } 

p2627 mowing the lawn g

大意

有一个长度为(n)的序列,选出若干个元素,使得选出的元素没有连续超过(k)个的((0<k<=n)),求选出元素的和的最大值。

思路

选出的数的和的最大值可以转换成删去的数的和的最小值。

代码
#include<iostream> #include<cstdio> #define maxn 100005 using namespace std; long long n,k,a[maxn],f[maxn]; long long q[maxn],h=0,t=0; long long tot=0; void push(long long x,long long l){ 	while(f[x]<f[q[t]]&&h<=t){ 		t--; 	} 	while(q[h]<l&&h<=t){ 		h++; 	} 	q[++t]=x; } int main(){ 	scanf("%lld%lld",&n,&k); 	for(long long i=1;i<=n;i++){ 		scanf("%lld",&a[i]); 		tot+=a[i]; 	} 	for(int i=1;i<=n;i++){ 		f[i]=f[q[h]]+a[i]; 		push(i,i-k); 	} 	long long mmin=f[n-k]; 	for(long long i=n-k+1;i<=n;i++){ 		mmin=min(f[i],mmin); 	} 	printf("%lld",tot-mmin); 	return 0; } /* 5 4 1 2 3 4 5 */ 

双倍经验:p2034 扫描

玉米实验

大意

给定一个(n*n)的矩阵(a),有(t)次询问,每次询问以((x_i,y_i))为左上角、长宽均为(k)的矩阵中,最大值与最小值的差值是多少。

思路

首先,我们还是显然能得出暴力的代码:
(ans_i = maxlimits_{x=x_i , y=y_i}^{x_i+k-1 , y_i+k-1}{a_{{x},{y}}} – minlimits_{x=x_i , y=y_i}^{x_i+k-1 , y_i+k-1}{a_{{x},{y}}})
然后,由于(k)是给定的,这让我们想到可以用单调队列优化(max(a_{{x},{y}}))(min(a_{{x},{y}})),即预处理矩阵(a),算出矩阵每一行的长(k)的滑动窗口中的最值,询问时直接查询子矩阵第一列的最值即可。

代码
#include<iostream> #include<cstdio> #include<cstring> #define maxn 1005 #define inf 99999999 using namespace std; int n,k,t,x,y; int a1[maxn][maxn],a2[maxn][maxn]; int q1[maxn],q2[maxn],h1=1,t1=0,h2=1,t2=0; int ans1[maxn][maxn],ans2[maxn][maxn]; void push1(int i,int x,int l){//找最小值  	while(a1[i][x]<a1[i][q1[t1]]&&h1<=t1){ 		t1--; 	} 	q1[++t1]=x; 	while(q1[h1]<l&&h1<=t1){ 		h1++; 	} } void push2(int i,int x,int l){//找最大值  	while(a2[i][x]>a2[i][q2[t2]]&&h2<=t2){ 		t2--; 	} 	q2[++t2]=x; 	while(q2[h2]<l&&h2<=t2){ 		h2++; 	} } void doit(int i){ 	memset(q1,0,sizeof(q1)); 	memset(q2,0,sizeof(q2)); 	h1=1;t1=0;h2=1;t2=0; 	q1[++t1]=1;q2[++t2]=1; 	for(int j=2;j<k;j++){ 		push1(i,j,-1); 		push2(i,j,-1); 	} 	for(int j=k;j<=n+k;j++){ 		push1(i,j,j-k+1); 		push2(i,j,j-k+1); 		ans1[i][j-k+1]=q1[h1]; 		ans2[i][j-k+1]=q2[h2]; 	} } int main(){ 	memset(a1,0x3f,sizeof(a1)); 	scanf("%d%d%d",&n,&k,&t); 	for(int i=1;i<=n;i++){ 		for(int j=1;j<=n;j++){ 			scanf("%d",&a1[i][j]); 			a2[i][j]=a1[i][j]; 		} 	} 	for(int i=1;i<=n;i++){ 		doit(i); 	} //	printf("n"); //	for(int i=1;i<=n;i++){ //		for(int j=1;j<=n;j++){ //			printf("%d ",a2[i][ans2[i][j]]); //		} //		printf("n"); //	} //	printf("n"); 	while(t--){ 		scanf("%d%d",&x,&y); 		int mmax=-1,mmin=inf; 		for(int i=0;i<k;i++){ 			mmax=max(mmax,a2[x+i][ans2[x+i][y]]); 			mmin=min(mmin,a1[x+i][ans1[x+i][y]]); 		} 		printf("%dn",mmax-mmin); 	} 	return 0; }  /* 5 3 2 5 1 2 6 3 1 3 5 2 7 7 2 4 6 1 9 9 8 6 5 0 6 9 3 9 2 1 1 2 */ 

p4954 [usaco09open]tower of hay g

大意

有一长(n)的序列,从左至右把它分成若干段,使得每一段的元素和都小于等于后一段的元素和,求出最大段数。

思路

我们先倒序读入序列,这样只要让每一段序列元素和大于等于后一段元素和即可。(sum_i)为前缀和。

首先是暴力。
我们设(f_i)为前(i)个元素的最优情况,且(len_i)表示此最优情况下最后一段序列的元素和最小值。这样我们不难推出表达式:(f_i=max(f_j)+1(0le j < i , sum_i – sum_jge len_j))即若(jsim i)区间内的元素和大于(len_j),也就是前(j)个的最小宽度,就可以再在(i)处分一段。
代码能卡过洛谷的数据。

#include<iostream> #include<cstdio> #define maxn 100005 using namespace std; int n; int a[maxn],sum[maxn],len[maxn],f[maxn]; int main(){ 	scanf("%d",&n); 	for(int i=n;i>=1;i--){ 		scanf("%d",&a[i]); 	} 	for(int i=1;i<=n;i++){ 		sum[i]=sum[i-1]+a[i]; 	} 	for(int i=1;i<=n;i++){ 		for(int j=i-1;j>=0;j--){ 			if(sum[i]-sum[j]>=len[j]){ 				f[i]=f[j]+1; 				len[i]=sum[i]-sum[j]; 				break; 			} 		} 	} 	printf("%d",f[n]); 	return 0;	 }  

但是,我们还是要改进一下,要不然不符合单调队列优化的标题
注意到(max(f_j))看着可以用单调队列优化,于是我们研究一下:
(sum_i – sum_jge len_j)移项,变成(sum_ige len_j + sum_j),这时,我们就可以维护单调队列,存所有满足以上式子的(j),最后直接求出(max(f_j))即可。

需要了解更多c/c++开发分享栈与队列(含单调栈与单调队列),都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!

代码
#include<iostream> #include<cstdio> #define maxn 100005 using namespace std; int n; int a[maxn],sum[maxn],len[maxn],f[maxn]; int q[maxn],h=1,t=1; int digit(int x){ 	return sum[x]+len[x]; } int main(){ 	scanf("%d",&n); 	for(int i=n;i>=1;i--){ 		scanf("%d",&a[i]); 	} 	for(int i=1;i<=n;i++){ 		sum[i]=sum[i-1]+a[i]; 	} 	for(int i=1;i<=n;i++){ 		int j=-1; 		while(h<=t&&sum[i]>=digit(q[h])){ 			j=q[h++]; 		} 		if(j!=-1){ 			q[--h]=j; 		} 		f[i]=f[q[h]]+1; 		len[i]=sum[i]-sum[q[h]]; 		while(h<=t&&digit(i)<digit(q[t])){ 			t--; 		} 		q[++t]=i; //		for(int j=i-1;j>=0;j--){ //			if(sum[i]-sum[j]>=len[j]){ //				f[i]=f[j]+1; //				len[i]=sum[i]-sum[j]; //				break; //			} //		} 	} 	printf("%d",f[n]); 	return 0;	 }  
www.ctvol.com true Article c/c++语言开发共享栈与队列(含单调栈与单调队列)

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/643507.html

(0)
上一篇 2021年7月2日 上午9:47
下一篇 2021年7月2日 上午9:49

精彩推荐