带配额的文件系统

目录

前情提要

题目背景

文件系统概述

配额概述

题目描述

创建普通文件

移除文件

设置配额值

输入格式

输出格式

样例1输入

样例1输出

样例1解释

样例2输入

样例2输出

样例2解释

子任务

我的思路

代码

满分代码

自己的代码

前情提要

这题来自于2020年12月ccf第三题，题目逻辑较于上次的DHCP更复杂，也因此我写出了很多bug，手动狗头，嗐，代码不完善，后续填坑。

题目背景

小 H 同学发现，他维护的存储系统经常出现有人用机器学习的训练数据把空间占满的问题，十分苦恼。

查找了一阵资料后，他想要在文件系统中开启配额限制，以便能够精确地限制大家在每个目录中最多能使用的空间。

文件系统概述

文件系统，是一种树形的文件组织和管理方式。在文件系统中，文件是指用名字标识的文件系统能够管理

的基本对象，分为普通文件和目录文件两种，目录文件可以被简称为目录。目录中有一种特殊的目录被叫做根目录。

除了根目录外，其余的文件都有名字，称为文件名。合法的文件名是一个由若干数字（[0-9]）、

大小写字母（[A-Za-z]）组成的非空字符串。普通文件中含有一定量的数据，占用存储空间；目录不占用存储空间。

文件和目录之间存在含于关系。上述概念满足下列性质：

有且仅有一个根目录；对于除根目录以外的文件，都含于且恰好含于一个目录；含于同一目录的文件，它们的文件名互不相同；对于任意不是根目录的文件f，若f不含于根目录，那么存在有限个目录d1,d2,…,dn，

使得f含于d1，d1含于d2，…，dn含于根目录。

结合性质 4 和性质 2 可知，性质 4 中描述的有限多个目录，即诸di，是唯一的。再结合性质 3，

我们即可通过从根目录开始的一系列目录的序列，来唯一地指代一个文件。我们记任意不是根目录且不含于

根目录的文件f的文件名是Nf，那么f的路径是：‘/′+Ndn+‘/′+⋯+Nd1+‘/′+Nf，其中符号+表示字符串的连接；对于含于根目录的文件f，

它的路径是：‘/′+Nf；根目录的路径是：‘/′。不符合上述规定的路径都是非法的。例如：/A/B

是合法路径，但/A//B、/A/、A/、A/B都不是合法路径。

若文件f含于目录d，我们也称f是d的孩子文件。d是f的双亲目录。

我们称文件f是目录d的后代文件，如果满足：(1)f是d的孩子文件，或(2)

f含于d的后代文件。

如图所示，该图中绘制的文件系统共有 8 个文件。其中，方形表示目录文件，圆形表示普通文件，它们之间

的箭头表示含于关系。在表示文件的形状上的文字是其文件名；各个形状的左上方标记了序号，以便叙述。

在该文件系统中，文件 5 含于文件 2，文件 5 是文件 2 的孩子文件，文件 5 也是文件 2 的后代文件。

文件 8 是文件 2 的后代文件，但不是文件 2 的孩子文件。文件 8 的路径是/D1/D1/F2。

配额概述

配额是指对文件系统中所含普通文件的总大小的限制。

对于每个目录d，都可以设定两个配额值：目录配额和

后代配额。我们称目录配额LDd是满足的，当且仅当d的孩子文件中，

全部普通文件占用的存储空间之和不大于该配额值。我们称后代配额LRd

是满足的，当且仅当d的后代文件中，全部普通文件占用的存储空间之和不大于该配额值。

我们称文件系统的配额是满足的，当且仅当该文件系统中所有的配额都是满足的。

很显然，若文件系统中仅存在目录，不存在普通文件，那么该文件系统的配额一定是满足的。随着配额和文件

的创建，某个操作会使文件系统的配额由满足变为不满足，这样的操作会被拒绝。例如：试图设定少于目前已有

文件占用空间的配额值，或者试图创建超过配额值的文件。

题目描述

在本题中，假定初始状态下，文件系统仅包含根目录。你将会收到若干对文件系统的操作指令。对于每条指令，

你需要判断该指令能否执行成功，对于能执行成功的指令，在成功执行该指令后，文件系统将会被相应地修改。

对于不能执行成功的指令，文件系统将不会发生任何变化。你需要处理的指令如下：

创建普通文件

创建普通文件指令的格式如下：

C  

None

创建普通文件的指令有两个参数，是空格分隔的字符串和一个正整数，分别表示需要创建的普通文件的路径和

文件的大小。

对于该指令，若路径所指的文件已经存在，且也是普通文件的，

则替换这个文件；若路径所指文件已经存在，但是目录文件的，则该指令不能执行成功。

当路径中的任何目录不存在时，应当尝试创建这些目录；若要创建的目录文件与已有的同一双亲目录下的孩子

文件中的普通文件名称重复，则该指令不能执行成功。

另外，还需要确定在该指令的执行是否会使该文件系统的

配额变为不满足，如果会发生这样的情况，则认为该指令不能执行成功，反之则认为该指令能执行成功。

移除文件

移除文件指令的格式如下：

R 

None

移除文件的指令有一个参数，是字符串，表示要移除的文件的路径。

若该路径所指的文件不存在，则不进行任何操作。

若该路径所指的文件是目录，则移除该目录及其所有后代文件。

在上述过程中被移除的目录（如果有）上设置的配额值也被移除。

该指令始终认为能执行成功。

设置配额值

Q   

None

设置配额值的指令有三个参数，是空格分隔的字符串和两个非负整数，分别表示需要设置配额值的目录

的路径、目录配额和后代配额。

该指令表示对所指的目录文件，

分别设置目录配额和后代配额。若路径所指的文件不存在，或者不是目录文件，则

该指令执行不成功。

若在该目录上已经设置了配额，则将原配额值替换为指定的配额值。

特别地，若配额值为 0，

则表示不对该项配额进行限制。若在应用新的配额值后，该文件系统配额变为不满足，那么该指令执行不成功。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数n，表示需要处理的指令条数。

输入接下来会有n行，每一行一个指令。指令的格式符合前述要求。输入数据保证：对于所有指令，

输入的路径是合法路径；对于创建普通文件和移除文件指令，输入的路径不指向根目录。

输出格式

输出到标准输出。

输出共有n行，表示相应的操作指令是否执行成功。若成功执行，则输出字母Y；否则输出N。

样例1输入

10
C /A/B/1 1024
C /A/B/2 1024
C /A/B/1/3 1024
C /A 1024
R /A/B/1/3
Q / 0 1500
C /A/B/1 100
Q / 0 1500
R /A/B
Q / 0 1

Data

样例1输出

Y
Y
N
N
Y
N
Y
Y
Y
Y

Data

样例1解释

输入总共有 10 条指令。其中前两条指令可以正常创建两个普通文件。第三条指令试图创建/A/B/1/3，

但是/A/B/1已经存在，且不是目录，而是普通文件，不能再进一步创建孩子文件，因此执行不成功。

第四条指令试图创建/A，但是/A已经存在，且是目录，因此执行不成功。第五条指令试图删除/A/B/1/3，

由于该文件不存在，因此不对文件系统进行修改，但是仍然认为执行成功。第六条指令试图在根目录

增加后代配额限制，但此时，文件系统中的文件总大小是 2048，因此该限制无法生效，执行不成功。

第七条指令试图创建文件/A/B/1，由于/A/B/1已经存在，且是普通文件，因此该指令实际效果是

将原有的该文件替换。此时文件总大小是 1124，因此第八条指令就可以执行成功了。

第九条指令递归删除了/A/B目录和它的所有后代文件。此时文件系统中已经没有普通文件，因此第十条命令

可以执行成功。

样例2输入

9
Q /A/B 1030 2060
C /A/B/1 1024
C /A/C/1 1024
Q /A/B 1024 0
Q /A/C 0 1024
C /A/B/3 1024
C /A/B/D/3 1024
C /A/C/4 1024
C /A/C/D/4 1024

Data

样例2输出

N
Y
Y
Y
Y
N
Y
N
N

Data

样例2解释

输入共有 9 条指令。第一条指令试图为/A/B创建配额规则，然而该目录并不存在，因此执行不成功。

接下来的两条指令创建了两个普通文件。再接下来的两条指令分别在目录/A/B和/A/C创建了

两个配额规则。其中前者是目录配额，后者是后代配额。接下来的两条指令，创建了

两个文件。其中，/A/B/3超出了在/A/B的目录配额，因此执行不成功；但/A/B/D/3

不受目录配额限制，因此执行成功。最后两条指令，创建了两个文件。虽然在/A/C

没有目录配额限制，但是无论是/A/C下的孩子文件还是后代文件，都受到后代配额的限制，因此两条指令

执行都不成功。

子任务

本题目各个测试点的数据规模如下：

表格中，目录层次是指各指令中出现的路径中，/字符的数目。

所有输入的数字均不超过1018。

我的思路

思路请见我的代码

下面有两个版本代码

我的代码比较复杂而且还有错误，但是oj上提交对了20%，提示是运行错误，初步估计是堆爆了，但是有空再检查检查，把这个坑填上。也希望大佬帮我看看哪里错了。

代码 满分代码

#include
#include
#include

自己的代码

#include 
using namespace std;struct file;
const long long SUP=2e18; //定义一个无穷大struct dir
{string name="";long long size=0; //文件大小long long fsize=0; //普通文件大小long long LD=SUP, LR=SUP; //初始化大文件dir *child_dir=NULL; //孩子文件夹指针file *child_file=NULL; //孩子文件指针dir *brother_dir=NULL; //和自己位于同一文件夹下的兄弟文件夹指针file *brother_file=NULL; //和自己位于同一文件夹下的兄弟文件
};struct file
{string name="";long long size=0;file *brother_file=NULL;
};//在当前文件夹下查找文件或文件夹
typedef long long Status;
const Status Find_Dir=1;
const Status Find_File=2;
const Status Error=0;struct ptr_group
{dir *dir_ptr=NULL;file *file_ptr=NULL;
};Status Search(const dir &nowdir, string obj_name, ptr_group &find, ptr_group &last) {find.dir_ptr=NULL; find.file_ptr=NULL;//找文件夹dir *child_dir=nowdir.child_dir;while (child_dir) {if (child_dir->name==obj_name) {find.dir_ptr=child_dir; return Find_Dir;}last.dir_ptr=child_dir;child_dir=child_dir->brother_dir;}file *child_file=nowdir.child_file;while (child_file)   {if (child_file->name==obj_name) {find.file_ptr=child_file; return Find_File;}last.file_ptr=child_file;child_file=child_file->brother_file; }return Error;
}//创建命令
void Creat(queue &path, dir &nowdir, long long final_fliesize, long long &formersize, int &flag) {formersize=0;/*###几种不能够执行命令的情况，可以直接退出###*///如果标志不用执行该命令，那直接退出if (flag==0) return;//要满足LR限制if (nowdir.size+final_fliesize>nowdir.LR) {flag=0; return;}//size==2表示到了目标普通文件上一层目录,此时要满足LDif (path.size()==1&&nowdir.fsize+final_fliesize>nowdir.LD) {flag=0; return;} //可以创建文件或文件夹，首先获得当前操作文件或文件夹名称string tem=path.front(); path.pop(); ptr_group find;ptr_group last;Status state=Search(nowdir, tem, find, last);//没有找到目标文件或文件夹,新建一个if (state==Error) { if (path.empty()) { //路径队列为空，说明当前已经到最深文件夹了，直接创建文件file* p=new file;p->name=tem;p->size=final_fliesize;p->brother_file=nowdir.child_file; nowdir.child_file=p; //前插法创建文件}else {dir *p=new dir;p->name=tem;p->brother_dir=nowdir.child_dir; nowdir.child_dir=p; //前插法创建文件夹Creat(path, *p, final_fliesize, formersize, flag);}}//在当前目录下找到了普通文件，替换原来的文件else if (state==Find_File&&path.empty()) {formersize=find.file_ptr->size;find.file_ptr->size=final_fliesize;}//要创建一个不存在的目录文件但是和普通文件重名else if (state==Find_File) flag=0;//在命令路径下找到了和要创建普通文件的同名文件但是它是目录文件，不操作else if (state==Find_Dir&&path.empty()) flag=0;//在命令路径的过程中找到了文件夹但不与最终目标文件同名else Creat(path, *find.dir_ptr, final_fliesize, formersize, flag);
}//为了释放删除文件夹的空间
void DeleteTree(dir *delete_root) {file *delete_file=delete_root->child_file, *tem;while (delete_file) {tem=delete_file;delete_file=delete_file->brother_file;delete tem;}dir *delete_dir=delete_root->child_dir, *met;while (delete_dir) {met=delete_dir;delete_dir=delete_dir->brother_dir;DeleteTree(met);}delete delete_root;
}//移除文件命令
void Remove(queue &path, dir &root, long long &filesize, int &flag) {ptr_group find;ptr_group last;dir *nowdir=&root;flag=0;//判断是否存在该路径while (!path.empty()) {string tem=path.front(); path.pop();Status state=Search(*nowdir, tem, find, last);if (state==Error) return;else if (state==Find_File&&path.empty()) { //找到要删除的文件file *t=find.file_ptr;last.file_ptr->brother_file=find.file_ptr->brother_file;filesize=t->size;delete t;flag=1; return;}else if (state==Find_File&&!path.empty()) return;else if (state==Find_Dir&&path.empty()) { //找到要删的文件夹dir *t=find.dir_ptr;if (last.dir_ptr==NULL) {filesize=find.dir_ptr->size;nowdir->child_dir=find.dir_ptr->brother_dir;DeleteTree(find.dir_ptr);}else {last.dir_ptr->brother_dir=find.dir_ptr->brother_dir;filesize=find.dir_ptr->size;DeleteTree(t); }flag=2; return;}nowdir=find.dir_ptr;}  
}//Q command
void Qcommand(queue &path, dir &root, long long ld, long long lr, int &flag) {ptr_group find;ptr_group last;dir nowdir=root;flag=0;if (ld==0) ld=SUP;if (lr==0) lr=SUP;while (!path.empty()) {string tem=path.front(); path.pop();Status state=Search(nowdir, tem, find, last);if (state==Error||state==Find_File) return;else if (state==Find_Dir&&path.empty()) {if (find.dir_ptr->size<=lr&&find.dir_ptr->fsize<=ld) {find.dir_ptr->LR=lr; find.dir_ptr->LD=ld; flag=1; return;}}nowdir=*find.dir_ptr;}if (path.empty()) {if (root.size<=lr&&root.fsize<=ld) {root.LD=ld; root.LR=lr;flag=1; return;}}
}//更新文件夹尺寸和普通文件尺寸
void RenewSize(deque &renew_path, dir *root, long long size, long long formersize, const string &order, int flag) {ptr_group find;ptr_group last;dir *nowdir=root; if (order=="C") {nowdir->size=nowdir->size+size-formersize;while (renew_path.size()>1) {string tem=renew_path.front(); renew_path.pop_front();Search(*nowdir, tem, find, last);nowdir=find.dir_ptr;nowdir->size=nowdir->size+size-formersize;}nowdir->fsize=nowdir->fsize+size-formersize;}else { //order=="R"if (flag==1) { //删除文件nowdir->size-=size;string tem;while (renew_path.size()>1) {tem=renew_path.front(); renew_path.pop_front();Search(*nowdir, tem, find, last);nowdir=find.dir_ptr;nowdir->size-=size;}nowdir->fsize-=size;}else if (flag==2) {nowdir->size-=size;string tem;while (renew_path.size()>1) {tem=renew_path.front(); renew_path.pop_front();Search(*nowdir, tem, find, last);nowdir=find.dir_ptr;nowdir->size-=size;}}}
}//分析路径字符串
void AnalysePath(string &filepath, queue &path, deque &renew_path) { //清空地址队列while (!path.empty()) path.pop();while (!renew_path.empty()) renew_path.pop_front();//开始解析路径字符串string::iterator it=filepath.begin();string tem="";while (it!=filepath.end()) {if (*it=='/') {if (tem=="") it++;else {path.push(tem); renew_path.push_back(tem); tem=""; it++;}}else {tem+=*it; it++;}}if (tem!="") {path.push(tem); renew_path.push_back(tem);}
}//启动程序
int main() {//初始化基本变量int n; cin>>n;string order, filepath; long long filesize, ld, lr;queue path;deque renew_path;//初始化一个根文件dir root; root.name="ROOT";//执行每一条命令for (int i=0; i>order;//校验命令码if (order=="C") {cin>>filepath>>filesize;long long formersize=0;AnalysePath(filepath, path, renew_path);Creat(path, root, filesize, formersize, flag);if (flag) {RenewSize(renew_path, &root, filesize, formersize, order, flag); cout<<'Y'<>filepath;AnalysePath(filepath, path, renew_path);Remove(path, root, filesize, flag);RenewSize(renew_path, &root, filesize, filesize, order, flag);cout<<'Y'<>filepath>>ld>>lr;AnalysePath(filepath, path, renew_path);Qcommand(path, root, ld, lr, flag);if (flag) cout<<'Y'<