xdoj1065 Efficent Allocation 动态开点的线段树

xdoj1065 Efficent Allocation  动态开点的线段树

1065: Efficent Allocation

时间限制: 8 Sec  内存限制: 256 MB
提交: 24  解决: 3
[提交][状态][讨论版]

题目描述

由于XDOJ评测机的一些奇怪行为，本题时限调整到8s。

lx正在写一个内存分配器，支持下列操作：

（1） malloc(size)，分配一个大小为size字节的内存块，返回指向该内存块的指针。

（2） free(p)，释放起始地址是p的内存块。

lx使用的分配策略是：每次找出一段地址最低的，大小不小于size字节的未分配内存，然后把这段内存的前size字节分配出来，剩余的部分仍然是未分配内存。在释放内存时，把被释放的内存块和前后的未分配内存合并成一块更大的未分配内存。

这时lw告诉lx，该分配器可能运行缓慢，并且产生大量内存碎片。lx承认了前一点，但是对于后一点十分不服气。于是，lw决定模拟该分配器的行为以证明这一点。但是，这个分配器太慢了，因此lw需要用一个较快的方法模拟该分配器的行为。

假设分配器管理的内存地址从1开始，即可供分配的内存是[1,n]。

输入

多组数据（最多5组）。

每组数据，第一行，两个整数n、q，表示分配器管理的内存大小和操作的个数。
之后q行，每行是malloc(size)或free(p)，含义如题目描述所述。

数据保证：1<=n<=109，1<=q<=100000，1<=size<=n，p是之前已经分配的某个内存块的起始地址。

输出

对于每次malloc操作输出1行，若操作成功，输出分配的内存块的起始地址（十进制）。若分配失败，输出0。

样例输入

100 2
malloc(100)
free(1)
5 8
malloc(1)
malloc(1)
malloc(1)
malloc(1)
free(1)
free(3)
malloc(2)
free(4)

样例输出

1
1
2
3
4
0

提示

对于第二组样例，在第6次操作后，已经分配的内存块是[2,2]和[4,4]，空闲内存块是[1,1]、[3,3]和[5,5]。它们的大小都小于2，因此分配失败。

来源

XDU 2015.6月赛

对拍了无数组小数据都过了，然而还是WA了。。。一定是标程的问题。

代码：

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=6500100;
const int INF=(1<<29);

struct Node
{
    int l,r;
    int ms,ls,rs;
    int tag;
    int lch,rch;
};

struct SegTree
{
    Node T[maxn];
    int p,rt;
    int newnode(int l,int r,int has)
    {
        T[++p]=(Node){l,r,(r-l+1)*has,(r-l+1)*has,(r-l+1)*has,has,-1,-1};
        return p;
    }
    void init(int l,int r)
    {
        p=0;
        rt=newnode(l,r,1);
    }
    void push_down(int rt)
    {
        if(T[rt].lch==-1&&T[rt].rch==-1) return;
        if(T[rt].tag!=-1){
            int lch=T[rt].lch,rch=T[rt].rch,tag=T[rt].tag;
            T[lch].tag=T[rch].tag=tag;
            T[lch].ms=T[lch].ls=T[lch].rs=tag*(T[lch].r-T[lch].l+1);
            T[rch].ms=T[rch].ls=T[rch].rs=tag*(T[rch].r-T[rch].l+1);
            T[rt].tag=-1;
        }
    }
    void push_up(int rt)
    {
        int lch=T[rt].lch,rch=T[rt].rch;
        T[rt].ls=T[lch].ls;
        T[rt].rs=T[rch].rs;
        if(T[rt].ls==T[lch].r-T[lch].l+1) T[rt].ls+=T[rch].ls;
        if(T[rt].rs==T[rch].r-T[rch].l+1) T[rt].rs+=T[lch].rs;
        T[rt].ms=max(max(T[lch].ms,T[rch].ms),T[lch].rs+T[rch].ls);
    }
    int query(int siz,int rt)
    {
        if(T[rt].ms<siz) return 0;
        if(T[rt].ls>=siz) return T[rt].l;
        push_down(rt);
        int t=query(siz,T[rt].lch);
        if(t) return t;
        int m=(T[rt].l+T[rt].r)>>1;
        if(T[T[rt].lch].rs+T[T[rt].rch].ls>=siz) return m-T[T[rt].lch].rs+1;
        return query(siz,T[rt].rch);
    }
    void update(int L,int R,int c,int rt)
    {
        int l=T[rt].l,r=T[rt].r;
        if(L<=l&&r<=R){
            T[rt].ms=T[rt].ls=T[rt].rs=(r-l+1)*c;
            T[rt].tag=c;
            return;
        }
        int m=(l+r)>>1;
        if(T[rt].lch==-1&&T[rt].rch==-1){
            T[rt].lch=newnode(l,m,T[rt].tag);
            T[rt].rch=newnode(m+1,r,T[rt].tag);
        }
        push_down(rt);
        if(L<=m) update(L,R,c,T[rt].lch);
        if(R>m) update(L,R,c,T[rt].rch);
        push_up(rt);
    }
};SegTree sgt;
int n,q;
char op[maxn];int x;

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    while(cin>>n>>q){
        sgt.init(1,n);
        while(q--){
            scanf("%s",op);
            if(op[0]=='m'){
                sscanf(op,"malloc(%d)",&x);
                int L=sgt.query(x,sgt.rt);
                printf("%d
",L);
                if(L) sgt.update(L,L+x-1,0,sgt.rt);
            }
            else{
                sscanf(op,"free(%d)",&x);
                sgt.update(x,x,1,sgt.rt);
            }
        }
    }
    return 0;
}
View Code

暴力代码：

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29);

int a[maxn];
int n,q;
char op[maxn];int x;

int query(int x)
{
    for(int i=1;i<=n;){
        if(a[i]){
            bool tag=1;
            int j;
            for(j=i;j<=i+x-1;j++){
                if(a[j]) continue;
                else{
                    tag=0;break;
                }
            }
            if(tag) return i;
            else i=j+1;
        }
        else i++;
    }
    return 0;
}

void update(int L,int R,int c)
{
    REP(i,L,R) a[i]=c;
}

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out_duipai.txt","w",stdout);
    while(cin>>n>>q){
        MS0(a);
        REP(i,1,n) a[i]=1;
        while(q--){
            scanf("%s",op);
            if(op[0]=='m'){
                sscanf(op,"malloc(%d)",&x);
                int L=query(x);
                printf("%d
",L);
                if(L) update(L,L+x-1,0);
            }
            else{
                sscanf(op,"free(%d)",&x);
                update(x,x,1);
            }
        }
    }
    return 0;
}
View Code

数据生成器：

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29);

int n,q;
int op,x;

int main()
{
    freopen("in.txt","w",stdout);
    int T=1000;
    while(T--){
        n=rand()%71+1;q=rand()%1000+1;
        printf("%d %d
",n,q);
        while(q--){
            op=rand()%2+1;x=rand()%n+1;
            if(op==1) printf("malloc(%d)
",x);
            else printf("free(%d)
",x);
        }
    }
    return 0;
}
View Code

对拍：

#include<bits/stdc++.h>
#include<windows.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29);

int x,y;

int main()
{
    FILE *fp=fopen("out.txt","r"),*fp1=fopen("out_duipai.txt","r");
    int tag=1;
    while(~fscanf(fp,"%d",&x)){
        fscanf(fp1,"%d",&y);
        if(x==y) puts("ok");
        else{
            printf("wrong x=%d y=%d
",x,y);
            tag=0;
            Sleep(1000);
        }
    }
    puts(tag?"Accept":"Wrong");
    return 0;
}
View Code

 ===================================

更新。。。题意有坑。。。。。。释放p是指释放之前分配的以p为开头的连续内存块。。。

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29);

struct Node
{
    int l,r;
    int ms,ls,rs;
    int tag;
    int lch,rch;
};

struct SegTree
{
    Node T[maxn<<2];
    int p,rt;
    int newnode(int l,int r,int has)
    {
        T[++p]=(Node){l,r,(r-l+1)*has,(r-l+1)*has,(r-l+1)*has,has,-1,-1};
        return p;
    }
    void init(int l,int r)
    {
        p=0;
        rt=newnode(l,r,1);
    }
    void push_down(int rt)
    {
        if(T[rt].lch==-1&&T[rt].rch==-1) return;
        if(T[rt].tag!=-1){
            int lch=T[rt].lch,rch=T[rt].rch,tag=T[rt].tag;
            T[lch].tag=T[rch].tag=tag;
            T[lch].ms=T[lch].ls=T[lch].rs=tag*(T[lch].r-T[lch].l+1);
            T[rch].ms=T[rch].ls=T[rch].rs=tag*(T[rch].r-T[rch].l+1);
            T[rt].tag=-1;
        }
    }
    void push_up(int rt)
    {
        int lch=T[rt].lch,rch=T[rt].rch;
        T[rt].ls=T[lch].ls;
        T[rt].rs=T[rch].rs;
        if(T[rt].ls==T[lch].r-T[lch].l+1) T[rt].ls+=T[rch].ls;
        if(T[rt].rs==T[rch].r-T[rch].l+1) T[rt].rs+=T[lch].rs;
        T[rt].ms=max(max(T[lch].ms,T[rch].ms),T[lch].rs+T[rch].ls);
    }
    int query(int siz,int rt)
    {
        if(T[rt].ms<siz) return 0;
        if(T[rt].ls>=siz) return T[rt].l;
        push_down(rt);
        int t=query(siz,T[rt].lch);
        if(t) return t;
        int m=(T[rt].l+T[rt].r)>>1;
        if(T[T[rt].lch].rs+T[T[rt].rch].ls>=siz) return m-T[T[rt].lch].rs+1;
        return query(siz,T[rt].rch);
    }
    void update(int L,int R,int c,int rt)
    {
        int l=T[rt].l,r=T[rt].r;
        if(L<=l&&r<=R){
            T[rt].ms=T[rt].ls=T[rt].rs=(r-l+1)*c;
            T[rt].tag=c;
            return;
        }
        int m=(l+r)>>1;
        if(T[rt].lch==-1&&T[rt].rch==-1){
            T[rt].lch=newnode(l,m,T[rt].tag);
            T[rt].rch=newnode(m+1,r,T[rt].tag);
        }
        push_down(rt);
        if(L<=m) update(L,R,c,T[rt].lch);
        if(R>m) update(L,R,c,T[rt].rch);
        push_up(rt);
    }
};SegTree sgt;
int n,q;
char op[maxn];int x;
set<int> li,ri;
map<int,int> lr;

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    while(cin>>n>>q){
        sgt.init(1,n);
        li.clear();ri.clear();
        while(q--){
            scanf("%s",op);
            if(op[0]=='m'){
                sscanf(op,"malloc(%d)",&x);
                int L=sgt.query(x,sgt.rt);
                printf("%d
",L);
                if(L) sgt.update(L,L+x-1,0,sgt.rt),li.insert(L),lr[L]=L+x-1,ri.insert(L+x-1);
            }
            else{
                sscanf(op,"free(%d)",&x);
                set<int>::iterator it=li.find(x);
                if(it==li.end()) continue;
                set<int>::iterator it1=ri.find(lr[x]);
                sgt.update(*it,*it1,1,sgt.rt);
                li.erase(it);ri.erase(*it1);
            }
        }
    }
    return 0;
}
View Code
没有AC不了的题，只有不努力的ACMER！
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/--560/p/4997314.html