首页 > 代码库 > [BZOJ2006][NOI2010]超级钢琴

[BZOJ2006][NOI2010]超级钢琴

2024-09-18 16:13:46   220人阅读

在和yjj大神的讨论下做了出来。。。对于每个点作为左段点的区间"们"，找到价值最大的那个，删掉它，再在剩下的里面找最大的。

最大区间我们可以预处理出前缀和s[i]，因为左端点已确定，所以只要找s[i]最大的且符合长度限制的i即可，静态的区间最大有很多算法，反正我写了个线段树~\(≧▽≦)/~啦啦啦。

显然需要一个堆，然后每次删除其实就是把原区间分成了两段，再丢回堆里，分析了下复杂度，线段树和堆都是log的，每次区间分裂会多出一个，所以不会挂。

技术分享 
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#include<vector>
typedef long long LL;
using namespace std;
const int N=500010;
struct node{int l,r,mx,pos;}a[N<<2];
int n,m,L,R,b[N],s[N];
LL ans;
struct nodee
{
    int i,l,r,pos,v;
    bool operator < (const nodee &x) const{return x.v>v;}
};
priority_queue<nodee>q;
int read() {int d=0,f=1; char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1; c=getchar();} while (c>=‘0‘&&c<=‘9‘) d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;}
void judge(){freopen(".in","r",stdin); freopen(".out","w",stdout);}
void build(int k,int l,int r)
{
    a[k]=(node){l,r,0,0};
    if (l==r) {a[k].mx=s[l]; a[k].pos=l; return;}
    int mid=(l+r)>>1;
    int k1=k<<1,k2=k1|1;
    build(k1,l,mid); build(k2,mid+1,r);
    if (a[k1].mx>a[k2].mx) a[k].mx=a[k1].mx,a[k].pos=a[k1].pos;
    else a[k].mx=a[k2].mx,a[k].pos=a[k2].pos;
}
node query(int k,int l,int r)
{
    if (l<=a[k].l&&a[k].r<=r) return a[k];
    int mid=(a[k].l+a[k].r)>>1,k1=k<<1,k2=k1|1;
    if (r<=mid) return query(k1,l,r);
    else if (l>mid) return query(k2,l,r);
    else
    {
        node x=query(k1,l,mid),y=query(k2,mid+1,r);
        if (x.mx>y.mx) return x; else return y;
    }
}
int main()
{
    //judge();
    n=read(); m=read(); L=read(); R=read();
    for (int i=1;i<=n;i++) b[i]=read(),s[i]=s[i-1]+b[i];
    build(1,1,n);
    for (int i=1;i<=n;i++)
    {
        int x=i+L-1,y=i+R-1;
        if (x>n) continue; if (y>n) y=n;
        int pos=query(1,x,y).pos;
        nodee z;
        z.l=x; z.r=y; z.i=i; z.pos=pos; z.v=s[pos]-s[i-1];
        q.push(z);
    }
    while (m--)
    {
        nodee ljj=q.top(); q.pop();
        ans+=ljj.v;
        if (ljj.pos>ljj.l)
        {
            nodee pjy=ljj;
            pjy.r=ljj.pos-1;
            pjy.pos=query(1,pjy.l,pjy.r).pos;
            pjy.v=s[pjy.pos]-s[pjy.i-1];
            q.push(pjy);
        }
        if (ljj.pos<ljj.r)
        {
            nodee pjy=ljj;
            pjy.l=ljj.pos+1;
            pjy.pos=query(1,pjy.l,pjy.r).pos;
            pjy.v=s[pjy.pos]-s[pjy.i-1];
            q.push(pjy);
        }
    }
    printf("%lld",ans);
    return 0;
}
View Code

 

[BZOJ2006][NOI2010]超级钢琴


联系
我们