首页 > ACM题库 > HDU-杭电 > HDU 2871-Memory Control-线段树-[解题报告]HOJ
2014
02-17

HDU 2871-Memory Control-线段树-[解题报告]HOJ

Memory Control

问题描述 :

Memory units are numbered from 1 up to N.
A sequence of memory units is called a memory block.
The memory control system we consider now has four kinds of operations:
1.  Reset Reset all memory units free.
2.  New x Allocate a memory block consisted of x continuous free memory units with the least start number
3.  Free x Release the memory block which includes unit x
4.  Get x Return the start number of the xth memory block(Note that we count the memory blocks allocated from left to right)
Where 1<=x<=N.You are request to find out the output for M operations.

输入:

Input contains multiple cases.
Each test case starts with two integer N,M(1<=N,M<=50000) ,indicating that there are N units of memory and M operations.
Follow by M lines,each line contains one operation as describe above.

输出:

Input contains multiple cases.
Each test case starts with two integer N,M(1<=N,M<=50000) ,indicating that there are N units of memory and M operations.
Follow by M lines,each line contains one operation as describe above.

样例输入:

6 10
New 2
New 5
New 2
New 2
Free 3
Get 1
Get 2
Get 3
Free 3
Reset

样例输出:

New at 1
Reject New
New at 3
New at 5 
Free from 3 to 4
Get at 1
Get at 5
Reject Get
Reject Free
Reset Now

很综合的一道题额~考二分 不过 没用在线段树上~~

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int MAXN=50005;
int blocks[MAXN*2];
struct node
{
    int l,r;
    int msum,lsum,rsum;
    int lazy;
    int mid()
    {
        return (l+r)>>1;
    }
};
node tree[MAXN*4];
inline void pushup(int pos)
{
    tree[pos].msum=max(tree[lson].msum,tree[rson].msum);
    tree[pos].lsum=tree[lson].lsum;
    tree[pos].rsum=tree[rson].rsum;
    tree[pos].msum=max(tree[pos].msum,tree[lson].rsum+tree[rson].lsum);
    int l1=tree[lson].r-tree[lson].l+1;
    int l2=tree[rson].r-tree[rson].l+1;
    if(tree[lson].lsum==l1)
        tree[pos].lsum+=tree[rson].lsum;
    if(tree[rson].rsum==l2)
        tree[pos].rsum+=tree[lson].rsum;
}
inline void pushdown(int pos)
{
    if(tree[pos].lazy!=-1)
    {
        tree[lson].lazy=tree[pos].lazy;
        tree[rson].lazy=tree[pos].lazy;
        if(tree[pos].lazy==1)
        {
            tree[lson].lsum=tree[lson].rsum=tree[lson].msum=0;
            tree[rson].lsum=tree[rson].rsum=tree[rson].msum=0;
        }
        else
        {
            tree[lson].lsum=tree[lson].rsum=tree[lson].msum=
                tree[lson].r-tree[lson].l+1;
            tree[rson].lsum=tree[rson].rsum=tree[rson].msum=
                tree[rson].r-tree[rson].l+1;
        }
        tree[pos].lazy=-1;
    }
}
void build(int l,int r,int pos)
{
    tree[pos].l=l;
    tree[pos].r=r;
    if(l==r)
    {
        tree[pos].msum=1;
        tree[pos].lsum=tree[pos].rsum=1;
        tree[pos].lazy=-1;
        return ;
    }
    int mid=tree[pos].mid();
    build(l,mid,lson);
    build(mid+1,r,rson);
    pushup(pos);
    tree[pos].lazy=-1;
}
void update(int l,int r,int x,int pos)
{
    if(l==tree[pos].l&&r==tree[pos].r)
    {
        tree[pos].lazy=x;
        if(x==0)
        {
            tree[pos].lsum=tree[pos].rsum=tree[pos].msum=
                tree[pos].r-tree[pos].l+1;
        }
        else
        {
            tree[pos].lsum=tree[pos].rsum=tree[pos].msum=0;
        }
        return ;
    }
    pushdown(pos);
    int mid=tree[pos].mid();
    if(r<=mid)
        update(l,r,x,lson);
    else if(l>mid)
        update(l,r,x,rson);
    else
    {
        update(l,mid,x,lson);
        update(mid+1,r,x,rson);
    }
    pushup(pos);
}
int query(int x,int pos)
{
    if(tree[pos].msum<x)
        return 0;
    if(tree[pos].lsum>=x)
        return tree[pos].l;
    pushdown(pos);
    if(tree[lson].msum>=x)
        return query(x,lson);
    else if(tree[lson].rsum+tree[rson].lsum>=x)
        return tree[lson].r-tree[lson].rsum+1;
    else
        return query(x,rson);
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        build(1,n,1);
        char word[10];
        int i;
        int k=0;
        int ff=0;
        for(i=0;i<m;i++)
        {
            int x;
            scanf("%s",word);
            if(word[0]!='R')
                scanf("%d",&x);
            if(word[0]=='R')
            {
                update(1,n,0,1);
                printf("Reset Now\n");
                k=0;
            }
            else if(word[0]=='N')
            {
                int a=query(x,1);
                if(a==0)
                    printf("Reject New\n");
                else
                {
                    printf("New at %d\n",a);
                    update(a,a+x-1,1,1);
                    blocks[k++]=a;
                    blocks[k++]=a+x-1;
                    ff=0;

                }
            }
            else if(word[0]=='F')
            {
                if(ff==0)
                    sort(blocks,blocks+k),ff=1;
                int l=0,r=k-1;
                int res;
                while(l<=r)
                {
                    int mid=(l+r)>>1;
                    if(blocks[mid]>x)
                        r=mid-1;
                    else
                    {
                        l=mid+1;
                    }
                }
                res=l-1;
                if(res==-1)
                    printf("Reject Free\n");
                else if(blocks[res]==x)
                {
                    if(res%2==0)
                        l=res,r=res+1;
                    else
                        l=res-1,r=res;
                    printf("Free from %d to %d\n",blocks[l],blocks[r]);
                    update(blocks[l],blocks[r],0,1);
                    for(int j=r+1;j<k;j++)
                        blocks[j-2]=blocks[j];
                    k=k-2;
                }
                else
                {
                    if(res%2==0)
                    {
                        l=res,r=res+1;
                        printf("Free from %d to %d\n",blocks[l],blocks[r]);
                        update(blocks[l],blocks[r],0,1);
                        for(int j=r+1;j<k;j++)
                            blocks[j-2]=blocks[j];
                        k=k-2;
                    }
                    else
                    {
                        printf("Reject Free\n");
                    }
                }

            }
            else if(word[0]=='G')
            {
                if(ff==0)
                    sort(blocks,blocks+k),ff=1;
                if((x-1)*2>=k)
                    printf("Reject Get\n");
                else
                    printf("Get at %d\n",blocks[(x-1)*2]);
            }
        }
        printf("\n");
    }
    return 0;
}

解题参考:http://blog.csdn.net/juststeps/article/details/9567555


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧