算法标签

• 内存管理：模拟操作系统内存分配机制
• 时间戳管理：基于超时机制的内存块回收
• 贪心算法：总是分配最小可用块号
• 数据结构应用：使用set和map高效管理内存块

解题思路

1. 初始化：

   • 系统有$N=30000$个内存块，初始全部空闲（存储在free_blocks集合中）
   • 设置超时时间$T=600$秒（$10$分钟）

2. 请求处理流程：

   • 分配请求（<Time> +）：

     1. 清理已超时的内存块（free_expired_blocks）
     2. 从空闲集合中取出最小块号分配（allocate_block）
     3. 记录分配时间戳（当前时间$+T$）

   • 访问请求（<Time> . <BlockNo>）：

     1. 清理已超时的内存块
     2. 检查目标块是否在已分配映射中：
        • 存在：更新时间戳，返回+
        • 不存在：返回-

3. 关键数据结构：

   • set<int> free_blocks：维护有序空闲块（自动排序）
   • map<int, int> allocated_blocks：记录已分配块及其过期时间

4. 超时处理：

   • 每次请求前检查allocated_blocks，释放所有expiration_time ≤ current_time的块
   • 时间复杂度：$O(k)$（$k$为待释放块数）

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cstdlib> // for atoi
using namespace std;
 
const int N = 30000;
const int T = 600; // 10 minutes in seconds
 
set<int> free_blocks;
map<int, int> allocated_blocks; // block_no -> expiration_time 
 
void initialize_free_blocks() {
    for (int i = 1; i <= N; ++i) {
        free_blocks.insert(i); 
    }
}
 
void free_expired_blocks(int current_time) {
    vector<int> to_free;
    for (map<int, int>::iterator it = allocated_blocks.begin();  it != allocated_blocks.end();  ++it) {
        if (it->second <= current_time) {
            to_free.push_back(it->first); 
        }
    }
    for (size_t i = 0; i < to_free.size();  ++i) {
        int block = to_free[i];
        allocated_blocks.erase(block); 
        free_blocks.insert(block); 
    }
}
 
int allocate_block(int current_time) {
    int block = *free_blocks.begin(); 
    free_blocks.erase(free_blocks.begin()); 
    allocated_blocks[block] = current_time + T;
    return block;
}
 
bool access_block(int current_time, int block_no) {
    map<int, int>::iterator it = allocated_blocks.find(block_no); 
    if (it != allocated_blocks.end())  {
        it->second = current_time + T;
        return true;
    }
    return false;
}
 
int main() {
    initialize_free_blocks();
    string line;
    while (getline(cin, line)) {
        size_t space_pos = line.find('  ');
        int time = atoi(line.substr(0,  space_pos).c_str());
        char request_type = line[space_pos + 1];
        
        free_expired_blocks(time);
        
        if (request_type == '+') {
            int block = allocate_block(time);
            cout << block << endl;
        } else {
            size_t dot_pos = line.find('.',  space_pos + 1);
            int block_no = atoi(line.substr(dot_pos  + 1).c_str());
            if (access_block(time, block_no)) {
                cout << "+" << endl;
            } else {
                cout << "-" << endl;
            }
        }
    }
    return 0;
}