“心脏出血”
时间： 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;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。