2021.5.19 华为实习机试 题解：1 令牌 2 Huffman数的WPL 3 防火墙

第一题是一个模拟，编号为1-n的n个人做成一圈，
编号为i的人手上的令牌是i个，如果他被选出，
就把令牌交给下一个人
选择人的方式有正序和逆序两种，
正着数的第几个出局
倒着数的第几个出局

直接模拟，但是容易出bug

第二题：构建哈夫曼树，并返回最小代价WPL
WPL计算，使用优先队列，将所有节点看做单独的树，这样就构成了一个森林
每次从森林里面挑出最小的两个进行合并直到变成一个树

WPL = 所有叶子的权重*叶子深度求和
其实就是所有非叶子节点的权重求和，证明省略
其实在构建的过程中每次形成新的节点的时候将权重累加即可

// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>

using namespace std;

#define debug(x) cout<<#x<<": "<<(x)<<endl;

int help(vector<int>& a) {

    priority_queue<int,vector<int>,greater<int>> q;

    int t;
    for (int i : a) {
        q.push(i);
    }

    t = 0;
    while (q.size()>1){
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        t += a + b;
        q.push(a + b);
    }
    cout << t << endl;
    return t;
}

int main() {

    // [2,4,5,7]

    string s = "[2,4,5,7]";
    s = s.substr(1);
    s.pop_back();
    
    stringstream ss;
    ss << s;
    vector<int>a;
    a.reserve(100);
    string str;
    while (getline(ss,str,',')){
        a.push_back(stoi(str,0,10));
    }

    help(a);

    return 0;
}

第三题

区间查询

区间有左右端点和id
三种操作，插入 删除 查询
要求查询的复杂度不高于logn

查询给一个数，看这个数落在了哪一个区间 如果有多个选择id小的那个

感觉是二分查找，但是没有做出来