如果发现广告等破坏行为，请尽量将条目恢复到较早的版本而不是把相应内容直接删除，谢谢合作。

URAL/1037

来自"NOCOW"

跳转到: 导航, 搜索

目录

[编辑] withflying的解题报告

维护两个堆，一个是未使用的内存块，以块的序号为关键字；另一个是正在使用的内存块，以开始使用这内存块的时间为关键字并且记录pos数组，pos[i]=j表示第i个内存块在堆中的位置为j。读入的时候，每读入一个时间就和第二个堆的堆顶元素比较一下，如果相差超过600秒，就删除这个堆顶元素，插到第一个堆去。对于申请操作，只需要删第一个堆的堆顶，插到第二个堆去即可。对于询问一个内存块b，我们查询pos[b]是否为0，是输出-，否则输出+ 并且更新第二个堆pos[b]位置的元素（下翻）。我的代码比较丑陋，供大家BS。 

program cao;
const
  maxn=100000;
  maxblocks=30000;
  waiting=600;
 
var
  using,unused,pos,where:array[0..maxn] of longint;
  a,b,c,d,e,f,g,h,i,j,k,l,n,m,p,q,t,tmp:longint;
  ch:char;
 
procedure swap(var a,b:longint);
begin
  tmp:=a;
  a:=b;
  b:=tmp;
end;
 
procedure insert_unused(v:longint);
var
  i,j,k:longint;
begin
  inc(q);
  unused[q]:=v;
  i:=q;
  while i>1 do
    if unused[i]<unused[i shr 1] then
    begin
      swap(unused[i],unused[i shr 1]);
      i:=i shr 1;
    end
    else break;
end;
 
procedure deletetop_unused;
var
  i,j,k:longint;
begin
  unused[1]:=unused[q];
  dec(q);
  i:=1;
  while (i shl 1)<=q do
  begin
    j:=i shl 1;
    if (j+1<=q)and(unused[j]>unused[j+1]) then inc(j);
    if unused[i]>unused[j] then swap(unused[i],unused[j]);
    i:=j;
  end;
end;
 
procedure insert_using(time,mac:longint);
var
  i:longint;
begin
  inc(p);
  using[p]:=time;
  pos[mac]:=p;
  where[p]:=mac;
  i:=p;
  while i>1 do
    if using[i]<using[i shr 1] then
    begin
      swap(using[i],using[i shr 1]);
      swap(pos[where[i]],pos[where[i shr 1]]);
      swap(where[i],where[i shr 1]);
      i:=i shr 1;
    end
    else break;
end;
 
procedure maintain_using(v:longint);
var
  i,j,k:longint;
begin
  i:=v;
  while (i shl 1)<=p do
  begin
    j:=i shl 1;
    if (j+1<=p)and(using[j]>using[j+1]) then inc(j);
    if using[i]>using[j] then
    begin
      swap(using[i],using[j]);
      swap(pos[where[i]],pos[where[j]]);
      swap(where[i],where[j]);
    end;
    i:=j;
  end;
end;
 
procedure deletetop_using;
begin
  using[1]:=using[p];
  pos[where[p]]:=1;
  pos[where[1]]:=0;
  where[1]:=where[p];
  dec(p);
  if p<>0 then maintain_using(1);
end;
 
begin
  p:=0;
  q:=maxblocks;
  for i:=1 to maxblocks do
    unused[i]:=i;
  while not(eof) do
  begin
    read(t,ch,ch);
    while (p>0)and(using[1]+waiting<=t) do
    begin
      insert_unused(where[1]);
      deletetop_using;
    end;
    case ch of
      ‘+’:
        begin
          insert_using(t,unused[1]);
          writeln(unused[1]);
          deletetop_unused;
          readln;
        end;
      ‘.’:
        begin
          read(l);
          if pos[l]=0 then writeln(‘-’)
          else
          begin
            writeln(‘+’);
            using[pos[l]]:=t;
            maintain_using(pos[l]);
            readln;
          end;
        end;
    end;
  end;
end.


[编辑] --------boboo的解题报告

由于时限是2s，直接做不会超时的，但比较悬。 

program ural1037;
var
  i,j,k,num,time,t:longint;
  ch:char;
  a:array[0..30000]of longint;
begin
  for i:=1 to 30000 do
    a[i]:=-600;
  max:=1;
  while not seekeof do
  begin
    read(time,ch,ch);
    if ch='+'
      then begin
        t:=time-600;
        i:=1;
        while a[i]>t do inc(i);
        writeln(i);
        a[i]:=time;
      end
      else begin
        read(num);
        if time-a[num]>=600 then writeln('-')
           else begin
             writeln('+');
             a[num]:=time;
           end;
      end;
  end;
end.

http://hi.baidu.com/boboo%5Foi/blog/item/93a4d63f888ecceb55e7234a.html

http://hi.baidu.com/boboo_oi/blog

[编辑] Hakkinen（菜）的代码（不叫解题报告）

用两个堆，一个放用过的，一个放没用过的，供大家bs,想写线段树，但想不出来…… 

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define maxn 100000
#define mx 10000000
#define N 30001
 
typedef struct factor_
{
    long time;
    long key;
}factor;
 
typedef factor Heap[maxn];
 
long Pos[N*2]={0},Point[N*2]={0};
Heap H1={0},H2={0};
 
long Get(factor x,int type)
{
    if (type==1) {if (!x.key) return mx;else return x.key;}
    if (!x.time) return mx;else return x.time;
}
 
void MinHeapfy(Heap H,long x,int type)
{
    long Min=0;
    factor t;
    if ( x*2> H[0].key ) return;
    if ( Get(H[x],type) > Get(H[x*2],type) ) Min=x*2;
    if ( Get(H[x],type) > Get(H[x*2+1],type)
         && Get(H[x*2+1],type) < Get(H[x*2],type) )
         Min=x*2+1;
    if (Min)
    {
        t=H[x];H[x]=H[Min];H[Min]=t;
        if (type==2)
        {
            Pos[ Point[x] ]=Min;
            Pos[ Point[Min] ]=x;
            long temp=Point[Min];
                 Point[Min]=Point[x];
                 Point[x]=temp;
        }
        MinHeapfy(H,Min,type);
    }
    return;
}
 
factor DeleteMin(Heap H,int type)
{
    factor x=H[1];
    H[1]=H[ H[0].key ];
    if (type==2)
    {
        Pos[ H[H[0].key].key ]=1;
        Point[1]=H[1].key;
        Point[ H[0].key ]=0;
    }
    H[ H[0].key ].key=0;
    --H[0].key;
    MinHeapfy(H,1,type);
    return x;
}
 
long HeapIns(Heap H,factor Key,int type)
{
    H[++H[0].key]=Key;
    long x=H[0].key;
    factor t;
    while (1)
    {
        if (x==1) return 1;
        if ( Get(H[x],type) >= Get(H[x/2],type) ) return x;
        t=H[x];
        H[x]=H[x/2];
        H[x/2]=t;
        if (type==2)
        {
            Pos[ Point[x] ]=x/2;
            Pos[ Point[x/2] ]=x;
            long temp=Point[x/2];
                 Point[x/2]=Point[x];
                 Point[x]=temp;
        }
        x/=2;
    }
}
 
int main(void)
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    long i,j,x;
    char s[2]={0};
 
    memset(H1,0,sizeof(H1));
    memset(H2,0,sizeof(H2));
    for (i=1;i<=N;++i) H1[i].key=i;
    H1[0].key=N;
    H2[0].key=0;
 
    while ( !feof(stdin) )
    {
        scanf("%ld%s",&x,&s);
        while (1)
        {
            if ( x-H2[1].time>=600 && H2[0].key>0)
            {
                factor y=DeleteMin(H2,2);
                y.time=0;
                long z=HeapIns(H1,y,1);
                Pos[y.key]=0;
            }else break;
        }
        if ( !strcmp(s,"+") )
        {
            scanf("\n");
            factor y=DeleteMin(H1,1);
            printf("%ld\n",y.key);
            y.time=x;
            Pos[y.key]=HeapIns(H2,y,2);
            Point[ Pos[y.key] ]=y.key;
        }else
        {
            long y;
            scanf("%ld\n",&y);
            if (Pos[y])
            {
                printf("+\n");
                H2[ Pos[y] ].time=x;
                MinHeapfy(H2,Pos[y],2);
            }
            else printf("-\n");
        }
    }
    return 0;
}

[编辑] 其他一份解题报告

堆，利用两个不同意义的堆，一个是以编号为key的小根堆，表示空闲的内存；一个是以时间为key的小根堆（存的是根的编号），表示正在用的内存。每次更新正在用的内存堆，如果是写入操作，则把空闲的内存根的时间更新，然后移入正在用的堆，如果是询问操作，那就看它是否在正在用的内存堆里（一个pos[i]数组表示在正在用的内存堆的位置），如果在就把它的时间更新到当前时间，然后从pos[i]向下调整。

sunnywkn的线段树 

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int MaxN = 30000;
const int TT = 600;
 
typedef struct TreeNode * Tree;
struct TreeNode
{
    int min, l, r;
    Tree left, right;
}*root;
 
#define L T->left
#define R T->right
#define M (T->l + T->r >> 1)
 
Tree creat(Tree T, int from, int to)
{
    T = new TreeNode;
    T->l = from;
    T->r = to;
    T->min = 0;
    if (from != to)
    {
        L = creat(L, from, M);
        R = creat(R, M + 1, to);
    }
    return T;
}
 
Tree insert(Tree T, int time)
{
    if (T->l == T->r)
    {
        printf("%d\n", T->l);
        T->min = time + TT;
            return T;
    }
    if (time >= L->min) L = insert(L, time);
        else R = insert(R, time);
 
    T->min = min(L->min, R->min);
    return T;
}
 
Tree change(Tree T, int time, int no)
{
    if (T->l == T->r)
    {
        if (time < T->min)
        {
            puts("+");
            T->min = max(T->min, time + TT);
        }
        else puts("-");
        return T;
    }
    if (no <= M) L = change(L, time, no);
        else R = change(R, time, no);
 
    T->min = min(L->min, R->min);
    return T;
}
 
int main()
{
    root = creat(root, 1, MaxN);
    int time, x;
    while (scanf("%d", &time) != -1)
    {
        char p = ' ';
        while (p == ' ') p = getchar();
        if (p == '+')
            root = insert(root, time);
        else 
        {
            int no;
            scanf("%d", &no);    
            root = change(root, time, no);
        }
    }
    return 0;
}

就是两个操作 1：加入一个数 2：查找并修改一个数 维护一个min域

来自"http://www.nocow.cn/index.php/URAL/1037"
个人工具