网易互娱（9.27）

1/4

复盘一下第二题，感觉能做出来的，被输入搞崩了心态。

大概题意

自己写一个文件系统，可以查文件，创建文件，关联文件，删除文件。为每个文件分配一个通配符，要求选择尽可能小没使用的通配符分配。具体看样例。通配符用非负整数表示，
输入：
第一行是样例数T
第二行是操作数N
接下来N行就是操作
（题目保证输入合法，就是不会查不存在的文件）
open 返回通配符
dup 返回另一个通配符
dup2 关联 b->a
close 删除通配符
query 返回文件名

输入

2
10
open libc.so
open libm.so
open libdl.so
dup 2
dup2 0 2
close 0
query 1
query 2
query 3
open log.txt
11
open output.txt
dup2 0 1000000
close 0
open output2.txt
dup2 0 100000
close 0
open 1.txt
dup 100000
query 1
query 0
dup 100000

输出

0
1
2
3
libm.so
libc.so
libdl.so
0
0
0
0
1
output2.txt
1.txt
2

代码

解题思路

我的思路是每个文件对应一个集合，每个集合对应多个通配符。也就是文件和集合是一对一，通配符和集合是多对一。通配符最小化的实现用了一个最小堆回收删除的通配符，和当前的通配符比较，取最小的。

坑点：

1. 读入很坑。不要连着用cin和getline，cin读完后会留个回车，这会导致getline多读一行是回车。
2. 最好写成类，多组输入数据，要不每次都要初始化。
3. 变量多了起名一定要讲究，要不一会儿就把自己绕晕了。

   代码实现

#include<bits/stdc++.h>
using namespace std;
constexpr const int MAXVAL = 10005;
#define ABS(x) ((x) >= 0 ? (x) : -(x))
typedef long long ll;

// 八千三百万零二十
// 1 2 3 4 5 6 7 8

vector<string> readline(std::istream& stream = std::cin, 
                           const char delimetar = ' ');


struct fileManager
{
  public:
    int open(string file);
    int dup(int id);
    void dup2(int id, int new_id);
    void close(int id);
    string query(int id);
  private:
    priority_queue<int, std::vector<int>, std::greater<int>> unused; //回收id 
    unordered_map<int, int> id_to_set;      //  id->setName
    unordered_map<string, int> file_to_set; //  name->id
    vector<string> set_to_file;             //  setName->name
    int cnt = 0; //当前未分配最小值
    vector<int> fileSet;
    int generate();  // 分配一个id
};


int main() {

 int T;
 cin>>T;
 while(T--)
 {

    fileManager myfun;

    int N;
    cin>>N;
    string operate;
    getline(cin, operate);
    for (int i = 0; i < N; ++i)
    {
      /* code */
       vector<string> operate =  readline();

       if(operate[0] == "open")
       {
          string file = operate[1];
          int ans =  myfun.open(file);
          cout<<ans<<endl;

       }
       if(operate[0] == "dup")
       {

          int id = stoi(operate[1]);
          int ans = myfun.dup(id);  
          cout<<ans<<endl;  
       }


       if(operate[0] == "dup2")
       {
          int new_id = stoi(operate[2]);
          int  id = stoi(operate[1]);
          myfun.dup2(id, new_id);
       }
       if(operate[0] == "close")
       {
          int  id = stoi(operate[1]);
          myfun.close(id);
       }

       if(operate[0] == "query")
       {
          int  id = stoi(operate[1]);
          string ans =  myfun.query(id);
          cout<<ans<<endl; 
       }
    }
 } 

 return 0;
}


vector<string> readline(std::istream& stream , const char delimetar)
{
    std::vector<string> ans;
    std::string line;
    std::string now;

    getline(stream, line);

    istringstream record(line);
    while(getline(record, now, delimetar))
        ans.push_back(now);

    return ans; 
}

int fileManager::generate()
{
     int candidate = INT_MAX;
     if(!unused.empty()) candidate = unused.top();

     if(candidate<=cnt)
     {
        unused.pop(); 
     }
     else 
     {
        candidate = cnt;
        ++cnt;

        while(id_to_set.count(cnt)) cnt++;
     }
     return candidate;
}

int fileManager::open(string file)
{


  int ans = generate();
  if(!file_to_set.count(file))
  {
     // 创建集合 记录数目
     fileSet.push_back(1);
     file_to_set[file] = fileSet.size()-1;
     // 更新集合和文件名的映射
     set_to_file.push_back(file);
  }

 int setName = file_to_set[file];
 // 更新文件描述符到集合的映射
 id_to_set[ans] = setName;
 return ans;
}



int fileManager::dup(int id)
{
   int ans = generate();
   // 找到这个集合
   int setName = id_to_set[id];
   // 现在id指向这个集合
   id_to_set[ans] = setName;
   fileSet[setName]++;
   return ans;
}

void fileManager::close(int id)
{
   // 找到这个集合
   int setName = id_to_set[id];
   fileSet[setName]--;
   if(fileSet[setName] == 0)
   {
     string file = set_to_file[setName];
     // 删除该集合
     file_to_set.erase(file);
     set_to_file.erase(set_to_file.begin()+ setName);
   }

   // 删除文件描述符到集合的映射
   id_to_set.erase(id);
   // 回收文件描述符
   unused.push(id);
}

void fileManager::dup2(int id, int new_id)
{
    if(id_to_set.count(new_id))
    {
       close(new_id);
    }
   // 找到这个集合
   int setName = id_to_set[id];
  // 更新
   id_to_set[new_id] = setName;
   fileSet[setName]++;
}

string fileManager::query(int id)
{
   // 找到这个集合
     int setName = id_to_set[id];
     //找到名字
     string file = set_to_file[setName];
     return file;
}

错误分析

考试时候命名混乱，集合元素从1开始计数，比实际下标大1，导致一直报错。按行读入没有经验，出现了bug。