带配额的文件系统 第21次CCF-CSP计算机软件能力认证

过了一半测试用例

1.检查孩子和后代配额用dfs递归就行
2.回退操作使用string承接结果如果为N 就pop_back child

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<bits/stdc++.h>
using namespace std;

struct node {
    int Class; // 0:目录文件 1:普通文件 2:代表根目录
    string name; // 文件名称
    int size; // 文件大小 目录文件为0
    int LD; // 目录配额
    int LR; // 后代配额
    vector<node*> child; // 孩子文件
    
    node() {}
    node(int c, string n, int size) : Class(c), name(n), size(size) { 
        LD = 0; 
        LR = 0; 
    }
};

vector<string> change(string s) {
    vector<string> res;
    if (s.size() == 1) return res; // 根目录情况
    
    size_t start = 1; // 跳过第一个'/'
    size_t end = s.find("/", start);
    
    while (end != string::npos) {
        res.push_back(s.substr(start, end - start));
        start = end + 1;
        end = s.find("/", start);
    }
    
    if (start < s.size()) {
        res.push_back(s.substr(start));
    }
    
    return res;
}

struct node* root = new node(2, "root", 0);

// 计算目录的直接孩子中普通文件的总大小
int calcChildSize(node* dir) {
    int total = 0;
    for (node* child : dir->child) {
        if (child->Class == 1) { // 普通文件
            total += child->size;
        }
    }
    return total;
}

// 计算目录的所有后代中普通文件的总大小
int calcDescendantSize(node* dir) {
    int total = 0;
    for (node* child : dir->child) {
        if (child->Class == 1) { // 普通文件
            total += child->size;
        } else if (child->Class == 0) { // 目录文件
            total += calcDescendantSize(child);
        }
    }
    return total;
}

// 检查配额是否满足
bool checkQuota(node* dir) {
    // 检查目录配额
    if (dir->LD > 0) {
        int childSize = calcChildSize(dir);
        if (childSize > dir->LD) return false;
    }
    
    // 检查后代配额
    if (dir->LR > 0) {
        int descendantSize = calcDescendantSize(dir);
        if (descendantSize > dir->LR) return false;
    }
    
    // 递归检查所有子目录
    for (node* child : dir->child) {
        if (child->Class == 0 && !checkQuota(child)) {
            return false;
        }
    }
    
    return true;
}

// 检查从根到指定路径的所有目录的配额
bool checkQuotaOnPath(vector<string> file_path, int file_size, int depth, node* now) {
    if (depth == file_path.size()) {
        return checkQuota(root);
    }
    
    // 模拟添加文件后检查配额
    if (depth == file_path.size() - 1) {
        // 检查当前目录的目录配额
        if (now->LD > 0) {
            int childSize = calcChildSize(now) + file_size;
            // 检查是否有同名文件需要替换
            for (node* child : now->child) {
                if (child->name == file_path[depth] && child->Class == 1) {
                    childSize -= child->size; // 减去原文件大小
                    break;
                }
            }
            if (childSize > now->LD) return false;
        }
        
        // 检查所有祖先目录的后代配额
        return checkQuota(root);
    }
    
    // 继续向下查找
    for (node* child : now->child) {
        if (child->Class == 0 && child->name == file_path[depth]) {
            return checkQuotaOnPath(file_path, file_size, depth + 1, child);
        }
    }
    
    // 需要创建新目录的情况，继续检查
    return checkQuota(root);
}

string dfs_add(vector<string> file_path, int file_size, int depth, node* now) {
    if (file_path.size() == 0) return "N";
    
    if (depth == file_path.size() - 1) {
        // 到达目标目录，检查是否存在同名文件
        for (node* child : now->child) {
            if (child->name == file_path[file_path.size() - 1]) {
                if (child->Class == 1) {
                    // 替换普通文件
                    child->size = file_size;
                    return checkQuota(root) ? "Y" : "N";
                } else {
                    // 同名目录存在，无法创建
                    return "N";
                }
            }
        }
        
        // 创建新的普通文件
        node* temp = new node(1, file_path[file_path.size() - 1], file_size);
        now->child.push_back(temp);
        
        // 检查配额
        if (checkQuota(root)) {
            return "Y";
        } else {
            // 配额不满足，撤销操作
            now->child.pop_back();
            delete temp;
            return "N";
        }
    }
    
    // 查找下一级目录
    for (node* child : now->child) {
        if (child->Class == 0 && child->name == file_path[depth]) {
            return dfs_add(file_path, file_size, depth + 1, child);
        } else if (child->Class == 1 && child->name == file_path[depth]) {
            // 路径中有普通文件阻挡
            return "N";
        }
    }
    
    // 需要创建新目录
    node* temp = new node(0, file_path[depth], 0);
    now->child.push_back(temp);
    
    string result = dfs_add(file_path, file_size, depth + 1, temp);
    
    if (result == "N") {
        // 创建失败，撤销目录创建
        now->child.pop_back();
        delete temp;
    }
    
    return result;
}

void deleteNode(node* n) {
    for (node* child : n->child) {
        deleteNode(child);
    }
    delete n;
}

string dfs_del(vector<string> file_path, int depth, node* now) {
    if (file_path.size() == 0) return "Y";
    
    if (depth == file_path.size() - 1) {
        for (auto it = now->child.begin(); it != now->child.end(); ++it) {
            if ((*it)->name == file_path[file_path.size() - 1]) {
                deleteNode(*it);
                now->child.erase(it);
                return "Y";
            }
        }
        return "Y"; // 文件不存在也返回Y
    }
    
    // 查找下一级目录
    for (node* child : now->child) {
        if (child->name == file_path[depth]) {
            return dfs_del(file_path, depth + 1, child);
        }
    }
    
    return "Y"; // 路径不存在也返回Y
}

node* findNode(vector<string> file_path, int depth, node* now) {
    if (depth == file_path.size()) {
        return now;
    }
    
    for (node* child : now->child) {
        if (child->name == file_path[depth]) {
            return findNode(file_path, depth + 1, child);
        }
    }
    
    return nullptr;
}

string dfs_set(vector<string> file_path, int ld, int lr) {
    node* target = findNode(file_path, 0, root);
    
    if (target == nullptr || target->Class != 0) {
        return "N"; // 目录不存在或不是目录
    }
    
    // 保存原配额值
    int oldLD = target->LD;
    int oldLR = target->LR;
    
    // 设置新配额值
    target->LD = ld;
    target->LR = lr;
    
    // 检查配额是否满足
    if (checkQuota(root)) {
        return "Y";
    } else {
        // 恢复原配额值
        target->LD = oldLD;
        target->LR = oldLR;
        return "N";
    }
}

int main() {
    int n;
    cin >> n;
    
    while (n--) {
        string opt;
        cin >> opt;
        
        if (opt == "C") {
            string file_path;
            int file_size;
            cin >> file_path >> file_size;
            cout << dfs_add(change(file_path), file_size, 0, root) << endl;
        }
        else if (opt == "R") {
            string file_path;
            cin >> file_path;
            cout << dfs_del(change(file_path), 0, root) << endl;
        }
        else {
            string file_path;
            int ld, lr;
            cin >> file_path >> ld >> lr;
            cout << dfs_set(change(file_path), ld, lr) << endl;
        }
    }
    
    return 0;
}