文档章节

内存分配(POJ-1193 )

潘少online
 潘少online
发布于 2015/04/18 13:15
字数 1023
阅读 22
收藏 0

算法分析:

1.维护一个进程的链表,每个节点存有进程开始时间t,进程运行时间p, 

在内存中的首地址s,占用内存大小m,和下一节点指针。 

2.维护一个队列,表示还没有空间运行的进程。 

3.维护一个释放内存的最早时间nexttime,每读入一个新进程的时候,若 

进程开始时间不小于nexttime,表示有进程在这之前已结束(可能不止一 

个),将其从链表删除,并循环检测队首进程是否有空间运行,如果有,就 

将其先加入(注意开始时间要设为止刻的nexttime,而不是读入的值了)。 

最后将新读入的进程加入链表,或加入队列。 

对应的代码:

while (a[pos].t>=nexttime)  free_and_pop();   
if (!alloc(pos,a[pos].t)) { Q[tail++]=pos; }   
else nexttime=_cpp_min(nexttime,a[pos].t+a[pos].p);   
//删除结束的进程,加入队列进程,更新nexttime   
void free_and_pop()   
{   
       int pre=root,temp=inf;   
       for (int i=root;i;)   
       {   
              if (a[i].t+a[i].p==nexttime)   
              {   
                     if (i==root)    
                     {   
                            root=a[root].next;   
                            i=root;   
                     }   
                     else    
                     {   
                            i=a[pre].next=a[i].next;   
                     }   
              }   
              else    
              {   
                     if (a[i].t+a[i].p<temp) temp=a[i].t+a[i].p;   
                     pre=i;   
                     i=a[i].next;   
              }   
       }   
       while (head<tail)    
              if (!alloc(Q[head],nexttime)) break;    
              else { temp=_cpp_min(temp,a[Q[head]].t+a[Q[head]].p);++head;}   
              
              nexttime=temp;   
              
}

如此往复。。。读入结束后,再对残余的队列和链表处理完,算出结果,完毕。

程序源码(C++):

#include <iostream>   
#include <algorithm>   
#include <cmath>   
#include <vector>   
using namespace std;   
const int inf = 1<<28;   
int n,m;   
struct node   
{   
       int m,t,p,s,next;   
}a[10000];   
 
int Q[10000],head,tail,c,root,nexttime;   
 
//分配内存(插入链表)   
bool alloc(int pos,int t)   
{   
       if (!root || a[root].s-0>=a[pos].m)   
       {   
              a[pos].next=root;   
              root=pos;   
              a[pos].t=t;   
              a[pos].s=0;   
              return true ;   
       }   
       int i;   
       for (i=root;a[i].next!=0;i=a[i].next)   
       {   
              if (a[i].s+a[i].m-1+a[pos].m < a[a[i].next].s)   
              {   
            a[pos].next=a[i].next;   
            a[i].next=pos;   
            a[pos].s=a[i].s+a[i].m;   
            a[pos].t=t;   
            return true;   
              }   
       }   
       if (i && n-(a[i].s+a[i].m) >= a[pos].m)   
       {   
              a[i].next=pos;   
              a[pos].next=0;   
              a[pos].s=a[i].s+a[i].m;   
              a[pos].t=t;   
              return true;   
       }   
       return false;   
}   
//删除结束的进程,加入队列进程,更新nexttime   
void free_and_pop()   
{   
       int pre=root,temp=inf;   
       for (int i=root;i;)   
       {   
              if (a[i].t+a[i].p==nexttime)   
              {   
                     if (i==root)    
                     {   
                            root=a[root].next;   
                            i=root;   
                     }   
                     else    
                     {   
                            i=a[pre].next=a[i].next;   
                     }   
              }   
              else    
              {   
                     if (a[i].t+a[i].p<temp) temp=a[i].t+a[i].p;   
                     pre=i;   
                     i=a[i].next;   
              }   
       }   
       while (head<tail)    
              if (!alloc(Q[head],nexttime)) break;    
              else { temp=min(temp,a[Q[head]].t+a[Q[head]].p);++head;}   
              
              nexttime=temp;   
              
}   
//插入新读入的进程   
void insert(int pos)   
{   
       while (a[pos].t>=nexttime)  free_and_pop();   
       if (!alloc(pos,a[pos].t)) { Q[tail++]=pos; }   
       else nexttime=min(nexttime,a[pos].t+a[pos].p);   
}   
//处理最后的队列中的进程   
int SolveRemain()   
{   
    while (head<tail)   
    {   
        free_and_pop();   
    }   
    int lasttime=nexttime;   
    for (int i=root;i;i=a[i].next)   
    {   
        lasttime=max(lasttime,a[i].t+a[i].p);   
    }   
    return lasttime;   
}   
 
int main()   
{   
       cin>>n;
    head=tail=c=root=0;   
    nexttime=inf;   
    for (int i=1;;i++)   
    {   
              cin>>a[i].t>>a[i].m>>a[i].p;
        if (a[i].t==0 && a[i].m==0 && a[i].p==0) break;   
        insert(i);   
    }   
    cout<<SolveRemain()<<endl<<tail<<endl;   
    system("pause");   
    return 0;   
}


© 著作权归作者所有

共有 人打赏支持
潘少online
粉丝 12
博文 58
码字总数 107019
作品 2
深圳
程序员
私信 提问
网络流建模汇总结

因为网上Dinic模板大多不规范或者可以被卡,所以先贴出一份跑得比较快的Dinic模板(主要快在maxflow()里面,可以仔细体会)。 (以下题意请自行百度) 1.最优分配 poj1149 应该是很裸的题了。...

qq_35649707
2017/08/04
0
0
Bryce1010专题训练——最大流

版权声明:时间是有限的,知识是无限的,那就需要在有限的时间里最大化的获取知识。 https://blog.csdn.net/Firetocheat_/article/details/83419978 Bryce1010专题训练——最大流 Edmonds-Ka...

bryce1010
2018/10/26
0
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
82
1
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
selenium docker容器中浏览器闪退的问题

昨天在用selenium docker时,遇到一个莫名其妙的问题,火狐浏览器61.0.1被打开后,过2s左右就闪退,看日志报下面的问题: 网上各种搜答案,发现这是火狐的一个bug,目前貌似还是没有解决掉。...

Ivanli1990
2018/12/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

《大数据白皮书(2018年)》发布(解读版+完整版PPT)

数据观微信小编获悉,为更好促进大数据与实体经济融合,研判技术发展路径,总结管理痛点、描绘发展趋势,总结行业应用渗透路径,4月18日,在“2018大数据产业峰会”上,中国信息通信研究院(...

了凡川
9分钟前
0
0
从小白到月薪上万,一份完整的大数据路线分析出自我成长书单

大数据原理与实践 大数据分三大部分,包括:大数据基础、技术原理和创新实践。 大数据基础部分主要介绍大数据的基本概念、技术架构和大数据的应用场景; 第二部分大数据技术原理主要介绍大数...

董黎明
20分钟前
0
0
斗鱼直播确定赴美IPO 此前融资额已达70亿元

据最新消息,斗鱼直播高层人士向新京报证实,斗鱼直播确定赴美IPO(首次公开募股),此前融资额已达70亿元。 此前,多家媒体报道,由国内知名直播平台斗鱼(Douyu)已秘密提交赴美IPO文件。 ...

ThinkSNS官方帐号
22分钟前
0
0
虎牙直播在微服务改造方面的实践和总结

相比文字和图片,直播提供了人与人之间更丰富的沟通形式,其对平台稳定性的考验很大,那么倡导“以技术驱动娱乐”的虎牙直播(以下简称“虎牙”)是如何在技术上赋能娱乐,本文将为您介绍虎牙...

阿里云云栖社区
25分钟前
0
0
采用SpringBoot整合Mybatis框架插入数据时报错及解决

这两天做SpringBoot整合Mybatis项目的时候,插入时报错: 3:45:59.936 DEBUG [http-nio-8080-exec-8] o.s.w.s.m.m.a.ExceptionHandlerExceptionResolver 133 - Resolving exception from ha......

aiChuang
31分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部