“心脏出血”

“心脏出血”

时间: 1ms        内存:128M

描述:

2014年4月,一个开源加密库OpenSSL的严重漏洞“心脏出血”(Heartbleed)被披露,由于内存分配的处理不当,导致用户隐私如血液般涌出。

  

  听到此消息,霞姐深深感觉到

内存分配的重要性,于是她为自己设计了一个内存管理程序,她希望这个内存管理程序能够支持以下三种操作:

1.alloc n – 分配n字节的连续内存,并输出被分配的内存块的id;

2.erase x – 释放id为x的内存块;

3.defragment – 对内存进行碎片整理。

霞姐拥有长度为m字节的内存,当然她不希望她的内存管理程序出现“心脏出血”这样的漏洞,于是她对这个管理程序做出了详细的要求:

1.第一块成功分配的内存的id为1,第二块为2,以此类推;

2.执行alloc操作所开盘的内存必须是连续

的,如果有多块符合这一条件的内存块,选择最靠前的那块来分配。如果不能分配这个大小的连续空闲内存块,则输出NULL;

3.erase操作释放完的内存可以重新使用,如果要释

放的

内存块在内存中没有找到,则返回ILLEGAL_ERASE_ARGUMENT,如果分配成功则不输出任何东西;

4.defragment操作将使所有内存尽量向前靠近,不打乱他们原本的顺序。该操作不输出任何东西。

霞姐最喜欢有安全感的人了,你能不能帮她实现这个内存管理程序,赢得她的芳心呢。

Input

 第一行包括两个整数t和m(1<=t<=100;1<=m<=100),分别代表进行t次操作以及内存的大小为m字节。 

接下来的t行分别是t次操作,有三类操作: 

1. alloc n(1<=n<=100),n是正整数; 

2. erase x,x是任意的32位整数; 

3. defragment操作。

输入:

输出进行操作时会产生的输出消息。每个输出占一行。

输出:

输出进行操作时会产生的输出消息。每个输出占一行。

示例输入:

6 10 
alloc 5
alloc 3
erase 1
alloc 6
defragment
alloc 6

示例输出:

1
2
NULL
3

提示:

参考答案(内存最优[1120]):

#include<stdio.h>
#include<string.h>
int ne[110]={0};
int f(int m)
{
    int i,t;
    for(i=1;i<=m;i++)
        printf("%d ",ne[i]);
        printf("\n");
    return 0;

}
int main()
{
    int i,t;
    int n,m;
    int y;
    char a[20];
    scanf("%d%d",&n,&m);
    int x=0;
    int b=0;
    int qq=0,ww=0,max=0,qi=1;
    while(n--)
    {
        int qq=0,ww=0,max=0;
        scanf("%s",a);
        if(strcmp(a,"alloc")==0)
        {
            scanf("%d",&y);

                for(i=1;i<=m;i++)
                {
                    if(qq==0&&ne[i]==0)
                        ww++;
                    if(max<ww)
                        max=ww;
                    if(ne[i]!=0)
                        qq=1;
                    if(ne[i]==0&&ne[i-1]!=0&&i>=2)
                        qq=0,ww=1,qi=i;
                }
                if(max>=y)
                {
                    b++;
                    printf("%d\n",b);
                    for(i=qi;i<qi+y;i++)
                        ne[i]=b;

                }

                else
                    printf("NULL\n");


        }
        int ll=0;
        if(strcmp(a,"erase")==0)
        {
            scanf("%d",&y);
            for(i=1;i<=m;i++)
            {
                if(ne[i]==y)
                {

                    ne[i]=0;
                    x--;
                    ll=1;
                }


            }
            if(ll==0||y==0||y>b)
                printf("ILLEGAL_ERASE_ARGUMENT\n");

        }
        if(strcmp(a,"defragment")==0)
        {
            for(i=m;i>=1;i--)
                for(t=m;t>1;t--)
            {
                if(ne[t]!=0&&ne[t-1]==0)
                    {ne[t-1]=ne[t];
                    ne[t]=0;}
            }

        }
    }
    return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int a[102];
char s[102];
int main()
{
    int i,j,n,m,x;
    scanf("%d%d",&n,&m);
    int id=1;
    while(n--)
    {
        scanf("%s",s);
        if(s[0]=='a')
        {
            scanf("%d",&x);
            for(i=0; i<=m-x; i++)
            {
                for(j=0; j<x; j++)
                    if(a[i+j]!=0)
                        break;
                if(j==x)break;
            }
            if(i<=m-x)
            {
                for(j=i; j<i+x; j++)
                    a[j]=id;
                printf("%d\n",id++);
            }
            else printf("NULL\n");
        }
        else if(s[0]=='e')
        {
            scanf("%d",&x);
            int flag=1;
            for(i=0; i<m; i++)
                if(a[i]&&a[i]==x)
                    a[i]=0,flag=0;
            if(flag)printf("ILLEGAL_ERASE_ARGUMENT\n");
        }
        else
        {
            for(i=0,j=0; i<m; i++)
                if(a[i])
                    a[j++]=a[i];
            while(j<m)a[j++]=0;
        }
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注