首页 > 代码库 > hihocoder 1198 Memory Allocating Algorithm
hihocoder 1198 Memory Allocating Algorithm
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <iostream> 4 #include <string.h> 5 #include <limits.h> 6 #include <queue> 7 #include <vector> 8 #include <set> 9 #include <map> 10 #include <algorithm> 11 #define LL long long 12 13 using namespace std; 14 int N; 15 LL M; 16 vector<pair<LL, LL> > blank; 17 queue<pair<LL, LL> > usemem; 18 int cur = 1; 19 20 int find_blank(LL len) { 21 LL min_len = M; 22 int min_index = -1; 23 for (int i=0;i<blank.size();++i) { 24 if(blank[i].second-blank[i].first >= len) { 25 min_len = blank[i].second-blank[i].first; 26 min_index = i; 27 } 28 } 29 return min_index; 30 } 31 32 void insert_usemem(int i, LL len) { 33 usemem.push(make_pair(blank[i].first, blank[i].first+len)); 34 blank[i].first += len; 35 } 36 37 void erase_usemem() { 38 pair<LL, LL> p = usemem.front(); 39 int left = -1, right = -1; 40 for (int i=0;i<blank.size();++i) { 41 if (blank[i].second == p.first) { 42 left = i; 43 } else if (blank[i].first == p.second) { 44 right = i; 45 } 46 } 47 if (left>=0 && right<0) { 48 blank[left].second = p.second; 49 } else if (left<=0 && right>=0) { 50 blank[right].first = p.first; 51 } else if (left>=0 && right >=0) { 52 blank[left].second = blank[right].second; 53 blank.erase(blank.begin()+right); 54 } else { 55 blank.push_back(make_pair(p.first, p.second)); 56 } 57 usemem.pop(); 58 cur++; 59 } 60 61 int go(LL len) { 62 int index = find_blank(len); 63 //printf("need mem [%d], result [%d]...\n", int(len), index); 64 if (index < 0) { 65 erase_usemem(); 66 return -1; 67 } else { 68 insert_usemem(index, len); 69 //printf("insert in pos [%d]...\n", int(blank[index].first-len)); 70 } 71 return 0; 72 } 73 74 75 int main() 76 { 77 scanf("%d%lld", &N, &M); 78 blank.push_back(make_pair(0, M)); 79 for (int i=0;i<N;++i) { 80 LL len; 81 scanf("%lld", &len); 82 while(1) { 83 if (go(len) == 0) break; 84 } 85 } 86 while(!usemem.empty()) { 87 pair<LL, LL> p = usemem.front(); 88 printf("%d %lld\n", cur++, p.first); 89 usemem.pop(); 90 } 91 return 0; 92 }
hihocoder 1198 Memory Allocating Algorithm
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。