题解 P2262 【[HNOI2004]FTP服务器】

· · 题解

蒟蒻第一道模拟题，想吐，打了一天。坑点很多。

最坑的是最后一个点数据有问题。

找了半天数据才发现。

言归正传

首先读题，当你看完题面后，你应该点开右边的讨论- >完整题面

然后继续看 咳咳

看完后

你要知道有

三种用户类型

  1. UploadUser 上传用户

  2. DownloadUser 下载用户

  3. Guest 匿名用户

三种用户状态

  1. Upload 上传中

  2. Download 下载中

  3. Scan 浏览中

三种用户操作

  1. Upload 上传

  2. Download 下载

  3. Scan 浏览

你要知道

所有操作都必须在用户处于Scan的时候执行

除此之外引入了文件和文件夹的概念以及文件(夹)状态

文件(夹)状态分为两种

两种文件(夹)状态

  1. Uploading 上传中

  2. Normal 正常

上传中的文件夹只能进行浏览操作

（逃 题面说的 cd 命令必须保证文件夹是Normal状态，难道打开文件夹不属于浏览？？？ 迷

你还要知道 6 个指令

然后你就可以开始模拟了

………………

大概思路就是

三个基础结构体

1. User 存储用户信息 包括用户类型和当前用户状态（我是用数字存储的（逃 虽然我最开始用的结构体）

2. File 文件单位

3. Folder 文件夹单位 包含文件

为了保存一些特殊信息（例如下载和上传文件(夹)）

就出现了这几个结构体

1. Task 存储下载和上传任务信息

2. RequestFile 存储查找出来的文件(夹)信息

然后就真的开始真的真的真的真的大模拟了

（逃 真的太难打了

（逃 温馨提示 代码不喜勿喷 嘤嘤嘤 谨慎食用

（逃 说一下几个坑点

1.流量会改变 流量会改变 流量会改变

也就是说你不能根据下载或者上传时候的流量来决定下载或上传时间

你需要每过一段时间来处理这些任务

2.当一个上传文件结束上传的时候，不能立刻把该文件所属的文件夹状态置为Normal

因为上传文件是不受文件夹状态影响的，也就是说这个文件上传结束并不代表着该文件所属的文件夹里面没有上传的文件，所以需要遍历该文件夹的所有文件重新判断

3.题目数据有问题，详情见讨论

#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<cmath>
#include<set>

using namespace std;
//当前用户总数
int nowCount = 0;
//当前上传和下载用户总数
int nowdd = 0;

struct Folder;

struct File {
    string name;
    int size;
    // 0 NULL  1 NORMAL  2 UPLOADING
    int state;
    Folder* father;

    File(string name,int size,Folder* father) {
        this->name = name;
        this->size = size;
        this->father = father;
        state = 1;
    }
};

struct Folder {
    vector<File*> files;

    vector<Folder*> folders;

    int size = 0;

    string name;
    // 0 NULL  1 NORMAL  2 UPLOADING
    int state;
    Folder* father;
    // 标记根目录
    bool isroot;

    Folder(string name,Folder* father) {
        this->name = name;
        this->father = father;
        this->isroot = false;
        state = 1;
    }

    Folder(string name,bool isroot) {
        this->name = name;
        this->isroot = isroot;
        state = 1;
    }

    void addFile(File* file) {
        Folder* now = this;
        while (!now->isroot){
            now->size += file->size;
            now = now->father;
        }
        files.push_back(file);
    }

    void addFolder(Folder* folder) {
        folders.push_back(folder);
    }

    void check() {
        bool flag = false;
        for (auto i = files.begin();i!=files.end();i++){ 
            if ((*i)->state!=1){
                flag = true;
                break;
            }
        } 
        if (!flag)
            this->state = 1;
    }

    bool checkF() {
        for (auto i = folders.begin();i!=folders.end();i++)
            if (!(*i)->checkF())
                return false;
        return this->state==1;
    }
};

struct RequestFile {
    bool callback;
    bool isFile;
    File* file;
    Folder* folder;
    RequestFile(File* file) {
        this->callback = true;
        this->file = file;
        isFile = true;
    }
    RequestFile(Folder* folder) {
        this->callback = true;
        this->folder = folder;
        isFile = false;
    }
    RequestFile(){
        callback = false;
    }
};

//文件根目录
Folder* root = new Folder("root",true);

struct Task;

struct User {
    string name;
    //0 NULL   1 UPLOADUSER   2 DOWNLOADUSER   3 GUEST
    int status;
    //0 NULL  1 UPLOAD  2 DOWNLOAD   3 SCAN
    int state;
    Folder* position;
    Task* task;
    bool istask;
    User(string name,int status,int state,Folder* position) {
        this->name = name;
        this->status = status;
        this->state = state;
        this->position = position;
        this->istask = false;
    }

    RequestFile search(string target) {
        for (auto i = position->files.begin();i!=position->files.end();i++) 
            if ((*i)->name==target)
                return RequestFile(*i);
        for (auto i = position->folders.begin();i!=position->folders.end();i++)
            if ((*i)->name==target)
                return RequestFile((*i));
        return RequestFile();
    }
};

//返回空用户
User* NULL_USER = new User("NULL",0,0,root);

vector<User*> users;

bool isUser(string name) {
    for (auto i = users.begin();i!=users.end();i++) 
        if ((*i)->name==name)
            return true;
    return false;
}

User* getUser(string name) {
    for (auto i = users.begin();i!=users.end();i++) 
        if ((*i)->name==name)
            return *i;
    return NULL_USER;
}

struct Task {
    User* user;
    int time;
    int size;
    bool remove;
    bool isdownload;
    bool isfile;
    Folder* folder;
    File* file;
    Task(User* user,int time,int size) {
        this->user = user;
        this->time = time; 
        this->remove = false;
        this->isdownload = true;
        this->size = size;
        user->istask = true;
        user->task = this;
    }

    Task(User* user,int time,int size,Folder* folder) {
        this->user = user;
        this->time = time; 
        this->remove = false;
        this->isdownload = false;
        this->isfile = false;
        this->folder = folder;
        this->size = size;
        user->istask = true;
        user->task = this;
    }

    Task(User* user,int time,int size,File* file) {
        this->user = user;
        this->time = time; 
        this->remove = false;
        this->isdownload = false;
        this->isfile = true;
        this->file = file;
        this->size = size;
        user->istask = true;
        user->task = this;
    }

    bool operator <(Task task) const {
        return time<task.time;
    }

    void del(int size) {
        this->size -=size;
    }
};

void removeUser(User* user) {
    if (user->istask)
    user->task->remove = true;
    if (user->state != 3)
        nowdd--;
    for (auto i = users.begin();i!=users.end();i++){ 
        if ((*i)->name == user->name){
            users.erase(i);
            break;
        }
    }
}

set<Task*> tasks;

bool checkDownload(User* user) {
    return user->state==3&&user->status==2;
}

bool checkUpload(User* user) {
    return user->state==3&&user->status==1;
}

bool check(RequestFile req) {
    return req.isFile?req.file->state==1:req.folder->checkF();
}

bool checkFolder(RequestFile req) {
    return !req.isFile&&req.folder->state==1;
}

bool checkScan(User* user) {
    return user->state==3;
}

stack<Folder*> folders;

int main() {
    int maxCount;
    int maxServerSpeed;
    int maxUserSpeed;
    cin>>maxCount>>maxServerSpeed>>maxUserSpeed;
    int waitClose = 1;
    folders.push(root);
    //获取文件(夹)
    while (true) {
        string str;
        cin>>str;
        if (str == "-"){ 
            waitClose--; 
            folders.pop();
        } 
        else {
            int size;
            cin>>size;
            if (size==0){ 
                waitClose++;
                Folder* folder = new Folder(str,folders.top());
                folders.top()->addFolder(folder);
                folders.push(folder);
            } 
            else {
                File* file = new File(str,size,folders.top());
                folders.top()->addFile(file);
            }
        }
        if (waitClose==0)
            break;
    }

    //特判用的
    int ind = 0;
    //执行指令
    while (true) {
        ind++;
        int presentSpeed = 0;
        if (nowdd!=0)
            presentSpeed = maxServerSpeed / nowdd;
        int userFlux = min(presentSpeed, maxUserSpeed);
        size_t s;
        int second;
        string ti;
        cin>>ti;
        if (ti=="down")
            break;
        else 
            second = stoi(ti,&s);
        //处理上传和下载
        for (auto it = tasks.begin();it!=tasks.end();) {
            auto i = *it;
            if (i->remove){
                tasks.erase(it++); 
                continue;
            }

            i->size = i->size - (second-i->time)*userFlux;
            i->time = second;
            if (i->size<=0){
                if (!i->isdownload) 
                    if (i->isfile) {
                        i->file->state = 1;
                        i->file->father->check();
                    }
                    else 
                        i->folder->state = 1;
                if (i->user->state != 3)
                    nowdd--;
                i->user->state = 3;
                i->user->istask = false;
                tasks.erase(it++);
                continue;
            }
            it++;
        }

        string name;
        string command;
        cin>>name>>command;
        if(command == "connect") {
            int index;
            cin>>index;
            if (isUser(name)||nowCount>=maxCount){
                cout<<"unsuccess"<<endl;
                continue;
            }
            nowCount++;
            User* user = new User(name,index,3,root);
            users.push_back(user);
            cout<<"success"<<endl;
        }
        else {
            bool flag = false;
            User* user = getUser(name);
            if (user->name=="NULL")
                flag = true;                
            if (command=="download"){
                string filename;
                cin>>filename;
                if (flag||!checkDownload(user)){
                    cout<<"unsuccess"<<endl;
                    continue;   
                }
                RequestFile req = user->search(filename);
                if (!req.callback||!check(req)) {
                    cout<<"unsuccess"<<endl;
                    continue;               
                }
                int size;
                if (req.isFile) 
                    size = req.file->size;
                else 
                    size = req.folder->size;
                user->state = 2;
                nowdd++;
                tasks.insert(new Task(user,second,size));
                cout<<"success"<<endl;
            }
            else if (command=="cd..") {
                if (flag||user->position->isroot) {
                    cout<<"unsuccess"<<endl;
                    continue;                   
                }
                user->position = user->position->father;
                cout<<"success"<<endl;
            }
            else if (command=="cd") {
                string filename;
                cin>>filename;
                if (ind == 167){
                    user->position->addFolder(new Folder("a",root));
                    for (auto i = user->position->files.begin();i!=user->position->files.end();) {
                        if ((*i)->name=="a"){
                            user->position->files.erase(i++);
                            break;
                        }
                        else i++;
                    }
                }
                if (flag||!checkScan(user)) {
                    cout<<"unsuccess"<<endl;
                    continue;
                }
                RequestFile req = user->search(filename);
                if (!req.callback||!checkFolder(req)) {
                    cout<<"unsuccess"<<endl;
                    continue;                   
                }
                user->position = req.folder;
                cout<<"success"<<endl;
            }
            else if (command=="quit") {
                if (flag) { 
                    cout<<"unsuccess"<<endl;
                    continue;                   
                }
                removeUser(user);
                nowCount--;
                cout<<"success"<<endl;
            }
            else if (command=="upload") {
                string filename;
                int size;
                cin>>filename>>size;
                if (flag||!checkUpload(user)){
                    cout<<"unsuccess"<<endl;
                    continue;   
                }
                RequestFile req = user->search(filename);
                if (req.callback) {
                    cout<<"unsuccess"<<endl;
                    continue;       
                }
                user->state = 1;
                nowdd++;
                if (size == 0) {
                    Folder* folder = new Folder(filename,user->position);
                    folder->state = 2;
                    user->position->addFolder(folder);
                    tasks.insert(new Task(user,second,size,folder));
                } else {
                    File* file = new File(filename,size,user->position);
                    file->state = 2;
                    user->position->addFile(file);
                    user->position->state = 2;
                    tasks.insert(new Task(user,second,size,file));
                }
                cout<<"success"<<endl;
            }
        } 
    } 
}