NOIP复赛复习(十九)栈与双端队列的运用

一、栈的运用

通过活用栈等简单的数据结构,可以巧妙地降低一些算法的复杂度。

POJ 2559

题意:n个宽度为1,高度为h[i](1<=i<=n)组成的柱形图,求里面包含的长方形的最大面积;

思路:如果确定了长方形的左端点L和右端点R,那么最大可能高度就是min{h[i]|L<=i<R}(一般做题区间都是左闭右开,便于计算),时间复杂度O(n^3),考虑优化区间最小值,可以降为O(n^2),但仍然无法在规定时间内求出答案。

考虑换种思路假设面积最大的长方形的左端为L,右端为R,高度为H。如果h[L-1]>=H,那么左端点可以更新为L-1,从而得到更大的长方形,与假设矛盾,故h[L-1]<H。同理,h[R]<H,并且高度H=min{h[i]|L<=i<R}。

做法:我们可以固定h[i]向左右方向延伸,则可以定义两个单调栈:L[i]=(j<=i并且h[j-1]<h[i]的最大的j)   R[i]=(j<i并且h[j]>h[i]的最小的j)

在计算L[i]时,首先,当栈顶的元素j满足h[j]>=h[i],则不断取出栈顶元素。若栈为空,则L[i]=0,若h[j]<h[i],则L[i]=j+1.然后把i压入栈中。

时间复杂度:由于栈的压入和弹出操作都是O(n)次,因此整个算法的时间复杂度为O(n)。对于R也可以用同样的方法计算。
#include<cstdio>
typedef long long ll;
const int maxn=100005;
ll a[maxn];
ll st[maxn];
ll l[maxn];
ll r[maxn];
ll max(ll aa,ll bb){
return aa>bb?aa:bb;
}
int main(){
int n;
//  freopen("in9.txt","r",stdin);
while(scanf("%d",&n)!=-1&&n){
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
int top=0;
for(int i=0;i<n;i++){
while(top&&a[st[top-1]]>=a[i]){
top--;
}
l[i]=top==0?0:st[top-1]+1;
st[top++]=i;
}
top=0;
for(int i=n-1;i>=0;i--){
while(top&&a[st[top-1]]>=a[i]){
top--;
}
r[i]=top==0?n:st[top-1];
st[top++]=i;
}
ll ans=0;
for(int i=0;i<n;i++){
ans=max(ans,((r[i]-l[i])*a[i]));
}
printf("%lldn",ans);
}
return 0;
}

二、双端队列的运用

队列是一种只允许在一端删除而在另一端插入的数据结构。双端队列(Deque)是队列的一种拓展,它可以在队列的两端进行插入和删除,它是限定插入和删除操作在表的两端进行的线性表,是一种具有队列和栈的性质的数据结构。

POJ 3709

题意:有一个不递减的序列,现在要把这些数分成若干个部分,每部分不能少于m个数。每部分的权值为所有数减去该部分最小的数的和。求最小的总权值。

首先不难得出,a0是最小的值,为了使操作的次数较小,我们不可能把最小值拿着减。所以我们发现,对于a0这样的较小的项,我们可以选择从小到大来选择需要减少到a0的项。设dpi为只考虑前i项的前提下最少的操作次数,则有dpi=min{dpj+(a[j+1]-a[j])+…+(a[i−1]-a[j])},其中0≤j≤i−k。

直接计算自然没问题,但是O3的复杂度不太好的样子,于是考虑优化:

例如我们记一个前缀和,

Si=a[0]+...+a[i−1]

有dpi=min{dpj+S[i]-S[j+1]-aj*(i-j-1)}
观察方程我们可以发现,若我们设一个函数(用x替换i)fj(x)=−aj∗x+dp[j]−S[j+1]+aj∗(j+1),则有dp[i]=S[i]+minfj(i),于是计算dp[n]就变为了在i-k+1条直线中寻找x=i的最小值就好了。
于是我们考虑用双端队列去维护所有可能成为最小值的直线的集合,并以从小到大的顺序排列。那么我们如何判断要去掉某条直线呢?

设:

f1(x)=a1∗x+b1
f2(x)=a2∗x+b2
f3(x)=a3∗x+b3

我们有(a2−a1)∗(b3−b2)≥(b2−b1)∗(a3−a2) 时,f2为要排除的直线。

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const ll maxn=505000;
ll cas=0;
ll n,k;
ll a[maxn];
ll deq[maxn];//虽然是双端队列但存的是值
ll dp[maxn*10];
ll sh[maxn];//前缀和
bool check(ll f1,llf2,ll f3)
{
ll a1=-a[f1];
ll b1=dp[f1]-sh[f1+1]+a[f1]*(f1+1);
ll a2=-a[f2];
ll b2=dp[f2]-sh[f2+1]+a[f2]*(f2+1);
ll a3=-a[f3];
ll b3=dp[f3]-sh[f3+1]+a[f3]*(f3+1);
return (a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2);
}
ll f(ll j,ll x)
{
return -a[j]*x+dp[j]-sh[j+1]+a[j]*(j+1);
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("2.out","w",stdout);
scanf("%lld",&cas);
for(ll z=0;z<cas;z++)
{
memset(sh,0,sizeof(sh));
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
memset(deq,0,sizeof(deq));
scanf("%lld%lld",&n,&k);
for(ll i=0;i<n;i++)
{
scanf("%lld",&a[i]);
}
for(ll i=0;i<n;i++)
{
sh[i+1]=sh[i]+a[i];
}
ll s=0;
ll t=1;
deq[s]=0;
dp[0]=0;
for(ll i=k;i<=n;i++)
{
if(i-k>=k)
{
while(s+1<t &&check(deq[t-2],deq[t-1],i-k))
{
t--;
}
deq[t]=i-k;
t++;
}
while(s+1<t &&f(deq[s],i)>=f(deq[s+1],i))
{
s++;
}
dp[i]=sh[i]+f(deq[s],i);
}
printf("%lldn",dp[n]);
}
return 0;
}

本文链接:NOIP复赛复习(十九)栈与双端队列的运用

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:少儿编程网,谢谢!^^


*文章为作者独立观点,不代表少儿编程网立场
发表评论

坐等沙发
相关文章
NOIP少年丨黄子桉:不骄不躁不傲慢不强求
NOIP少年丨黄子桉:不骄不躁不傲慢不强求
为什么越来越多家长选择信息学竞赛?
为什么越来越多家长选择信息学竞赛?
孩子学完各个阶段的编程课程能够参加哪些比赛?
孩子学完各个阶段的编程课程能够参加哪…
信息学竞赛必经之路–NOIP(内含2018报名方式说明)
信息学竞赛必经之路–NOIP(内含20…
我的孩子从来没有接触过编程,0基础能不能学?
我的孩子从来没有接触过编程,0基础能不…
新手想参加信息学竞赛NOIP ,如何入门进阶?
新手想参加信息学竞赛NOIP ,如何入门进…
NOIP2017 作者
NOI官网发布了2017年全国青少年信息学奥林匹克联赛(NOIP2017)的报名通知。NOIP2017将于2017年10月及11月分别举行初赛和复赛,有意向参加比赛的考生,即日起至10月10日可报名。