#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>

using namespace std;

// 分区结构体
struct Partition {
    int start;      // 起始地址
    int size;       // 分区大小
    bool allocated; // 是否已分配
    string process; // 进程名称（已分配分区使用）
    
    Partition(int s, int sz, bool alloc = false, string proc = "") 
        : start(s), size(sz), allocated(alloc), process(proc) {}
};

class MemoryManager {
private:
    vector<Partition> partitions;  // 分区列表
    int totalMemory;              // 总内存大小
    int nextFitIndex;             // 下次适应算法的起始位置
    
public:
    // 构造函数，初始化内存管理器
    MemoryManager(int total) : totalMemory(total), nextFitIndex(0) {
        // 初始化时整个内存为一个空闲分区
        partitions.push_back(Partition(0, total, false));
    }
    
    // 首次适应算法分配内存
    bool firstFit(string processName, int size) {
        cout << "使用首次适应算法为进程 " << processName << " 分配 " << size << " 单位内存" << endl;
        
        for (int i = 0; i < partitions.size(); i++) {
            // 找到第一个足够大的空闲分区
            if (!partitions[i].allocated && partitions[i].size >= size) {
                return allocatePartition(i, processName, size);
            }
        }
        
        cout << "分配失败：没有足够的连续空闲空间" << endl;
        return false;
    }
    
    // 下次适应算法分配内存
    bool nextFit(string processName, int size) {
        cout << "使用下次适应算法为进程 " << processName << " 分配 " << size << " 单位内存" << endl;
        
        int startIndex = nextFitIndex;
        int i = startIndex;
        
        // 从上次分配位置开始查找
        do {
            if (!partitions[i].allocated && partitions[i].size >= size) {
                nextFitIndex = i; // 更新下次查找的起始位置
                return allocatePartition(i, processName, size);
            }
            i = (i + 1) % partitions.size(); // 循环查找
        } while (i != startIndex);
        
        cout << "分配失败：没有足够的连续空闲空间" << endl;
        return false;
    }
    
    // 最佳适应算法分配内存
    bool bestFit(string processName, int size) {
        cout << "使用最佳适应算法为进程 " << processName << " 分配 " << size << " 单位内存" << endl;
        
        int bestIndex = -1;
        int minWaste = INT_MAX;
        
        // 查找最合适的分区（剩余空间最小）
        for (int i = 0; i < partitions.size(); i++) {
            if (!partitions[i].allocated && partitions[i].size >= size) {
                int waste = partitions[i].size - size;
                if (waste < minWaste) {
                    minWaste = waste;
                    bestIndex = i;
                }
            }
        }
        
        if (bestIndex != -1) {
            return allocatePartition(bestIndex, processName, size);
        }
        
        cout << "分配失败：没有足够的连续空闲空间" << endl;
        return false;
    }
    
    // 释放指定进程的内存
    bool deallocate(string processName) {
        cout << "释放进程 " << processName << " 的内存" << endl;
        
        bool found = false;
        for (int i = 0; i < partitions.size(); i++) {
            if (partitions[i].allocated && partitions[i].process == processName) {
                partitions[i].allocated = false;
                partitions[i].process = "";
                found = true;
                cout << "成功释放进程 " << processName << " 占用的内存" << endl;
            }
        }
        
        if (found) {
            mergePartitions(); // 合并相邻的空闲分区
            return true;
        }
        
        cout << "释放失败：未找到进程 " << processName << endl;
        return false;
    }
    
    // 显示当前内存分配状态
    void displayMemoryStatus() {
        cout << "\n===== 当前内存分配状态 =====" << endl;
        cout << "起始地址\t大小\t状态\t\t进程名" << endl;
        cout << "----------------------------------------" << endl;
        
        for (const auto& partition : partitions) {
            cout << partition.start << "\t\t" << partition.size << "\t";
            if (partition.allocated) {
                cout << "已分配\t\t" << partition.process;
            } else {
                cout << "空闲\t\t---";
            }
            cout << endl;
        }
        
        // 统计内存使用情况
        int usedMemory = 0;
        int freeMemory = 0;
        
        for (const auto& partition : partitions) {
            if (partition.allocated) {
                usedMemory += partition.size;
            } else {
                freeMemory += partition.size;
            }
        }
        
        cout << "----------------------------------------" << endl;
        cout << "总内存: " << totalMemory << " 单位" << endl;
        cout << "已用内存: " << usedMemory << " 单位" << endl;
        cout << "空闲内存: " << freeMemory << " 单位" << endl;
        cout << "内存利用率: " << fixed << setprecision(2) 
             << (double)usedMemory / totalMemory * 100 << "%" << endl;
        cout << "===========================\n" << endl;
    }
    
private:
    // 在指定位置分配分区
    bool allocatePartition(int index, string processName, int size) {
        Partition& partition = partitions[index];
        
        if (partition.size == size) {
            // 分区大小正好匹配，直接分配
            partition.allocated = true;
            partition.process = processName;
        } else {
            // 分区大小大于所需大小，需要分割
            int remainingSize = partition.size - size;
            
            // 修改当前分区为已分配
            partition.size = size;
            partition.allocated = true;
            partition.process = processName;
            
            // 在当前分区后插入剩余的空闲分区
            partitions.insert(partitions.begin() + index + 1, 
                            Partition(partition.start + size, remainingSize, false));
        }
        
        cout << "分配成功：为进程 " << processName << " 分配了 " << size << " 单位内存" << endl;
        return true;
    }
    
    // 合并相邻的空闲分区
    void mergePartitions() {
        // 按起始地址排序
        sort(partitions.begin(), partitions.end(), 
             [](const Partition& a, const Partition& b) {
                 return a.start < b.start;
             });
        
        // 合并相邻的空闲分区
        for (int i = 0; i < partitions.size() - 1; ) {
            if (!partitions[i].allocated && !partitions[i + 1].allocated &&
                partitions[i].start + partitions[i].size == partitions[i + 1].start) {
                
                // 合并两个相邻的空闲分区
                partitions[i].size += partitions[i + 1].size;
                partitions.erase(partitions.begin() + i + 1);
                
                // 重置下次适应算法的索引
                if (nextFitIndex > i) {
                    nextFitIndex--;
                }
            } else {
                i++;
            }
        }
    }
};

// 显示菜单
void displayMenu() {
    cout << "\n===== 可变分区内存管理系统 =====" << endl;
    cout << "1. 首次适应算法分配内存" << endl;
    cout << "2. 下次适应算法分配内存" << endl;
    cout << "3. 最佳适应算法分配内存" << endl;
    cout << "4. 释放内存" << endl;
    cout << "5. 显示内存状态" << endl;
    cout << "6. 退出系统" << endl;
    cout << "===============================" << endl;
    cout << "请选择操作: ";
}

int main() {
    cout << "欢迎使用可变分区内存管理系统!" << endl;
    cout << "请输入总内存大小: ";
    
    int totalMemory;
    cin >> totalMemory;
    
    MemoryManager memManager(totalMemory);
    
    int choice;
    string processName;
    int size;
    
    while (true) {
        displayMenu();
        cin >> choice;
        
        switch (choice) {
            case 1: // 首次适应算法
                cout << "请输入进程名: ";
                cin >> processName;
                cout << "请输入需要分配的内存大小: ";
                cin >> size;
                memManager.firstFit(processName, size);
                break;
                
            case 2: // 下次适应算法
                cout << "请输入进程名: ";
                cin >> processName;
                cout << "请输入需要分配的内存大小: ";
                cin >> size;
                memManager.nextFit(processName, size);
                break;
                
            case 3: // 最佳适应算法
                cout << "请输入进程名: ";
                cin >> processName;
                cout << "请输入需要分配的内存大小: ";
                cin >> size;
                memManager.bestFit(processName, size);
                break;
                
            case 4: // 释放内存
                cout << "请输入要释放的进程名: ";
                cin >> processName;
                memManager.deallocate(processName);
                break;
                
            case 5: // 显示内存状态
                memManager.displayMemoryStatus();
                break;
                
            case 6: // 退出系统
                cout << "感谢使用可变分区内存管理系统，再见!" << endl;
                return 0;
                
            default:
                cout << "无效选择，请重新输入!" << endl;
                break;
        }
    }
    
    return 0;
}