1599. 经营摩天轮的最大利润 #模拟

题目链接

题意

摩天轮(4)个座舱，每个座舱最多可容纳(4)位游客，座舱会轮转，且每次轮转需支付一定运行成本(runningCost)，且恰好转动(1/4)周。

给定长度为(n)的数组(customers)， (customers[i]) 是在第 (i) 次轮转之前到达的新游客的数量，即你必须在新游客到来前轮转(i) 次。每位游客在登上离地面最近的座舱前都会支付登舱成本 (boardingCost) ，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。注意，如果有超过 4 位游客在等摩天轮，那么只有恰好4 位游客可以登上摩天轮，其余的需要等待下一次轮转。你需要返回最大化利润所需执行的最小轮转次数。如果不存在利润为正的方案，则返回 (-1)。

样例

分析

利用队列去模拟摩天轮的四个舱位，之所以用队列，是因为该四个舱位的出现存在顺序，先来的游客便先获得机会登上座舱。但注意，每个座舱不一定坐满乘客！

class Solution {
private:
    queue<int> motian;
public:
    int minOperationsMaxProfit(vector<int>& customers, int boardingCost, int runningCost) {
        int last = 0, cur = 0, bonus = 0; //last表示当前等待中的游客数，cur表示摩天轮上登上舱的总人数，bonus表示利润
        int i = 0, ans = -0x3f3f3f3f, pos = -1; //pos表示取得最值时的操作次数 
        while(last != 0 || i < customers.size()){
            if(i < customers.size()) last += customers[i];
            if(last <= 4){
                cur += last;
                motian.push(last);
                last = 0;
            } 
            else {
                cur += 4;
                motian.push(4);
                last -= 4;
            }
            bonus = boardingCost * cur - runningCost * motian.size();
            if(ans < bonus){
                ans = bonus; pos = i;
            }
            i++;
        }   
        return (ans <= 0) ? -1 : pos + 1;
    }
};

1600. 皇位继承顺序 #C++类 #多叉树的先序遍历

题目链接

题意

题目看起来很长，简要概括为：

王国里住国王、其孩子们、孙子们等等。每一时间点，该家庭里有人出生或死亡。王国有皇位继承顺序，第一继承人总是国王自己，第二继承人为其最年长的儿子，第三继承人为该儿子的儿子，… ，直至没有后代了，再有继承人为国王第二个儿子，….，依次类推。

现要你实现 ThroneInheritance 类：

ThroneInheritance(string kingName); 初始化一个 ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。
void birth(string parentName, string childName); 表示 parentName 新拥有了一个名为 childName 的孩子。
void death(string name); 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
string[] getInheritanceOrder() 返回除去死亡人员的当前继承顺序列表。

分析

每个人都可能有多个或没有孩子，我们可以将用多叉树的结构去模拟；对于继承顺序，我们不难看出，实际就是多叉树的先序遍历，每次继承的是其第一个后代！由于数据规模不大，且加入新节点都是以string作为参数，于是我们用string映射含有多个string的向量。

const int MAXN = 1e5 + 5;
class ThroneInheritance {
private:
    string king;
    unordered_map<string, bool> isDeath; //名字映射布尔值，表示某个人是否死亡
    unordered_map<string, vector<string>> Order; //第一个key，映射一个vector，表示名字为key的后代存在vector中
public:
    ThroneInheritance(string kingName) {
        king = kingName;
        isDeath[kingName] = false;
    }
    void birth(string parentName, string childName) {
        Order[parentName].push_back(childName);
        isDeath[childName] = false;
    }
    void death(string name) {
        isDeath[name] = true;
    }
    void Successor(string cur, vector<string>& ans){ //利用DFS，确定继承
        int i = 0;
        for(int i = 0; i < Order[cur].size(); i++){
            string son = Order[cur][i];
            if(isDeath[son] == false) ans.push_back(son);
            Successor(son, ans);
        }
    }
    vector<string> getInheritanceOrder() {
        string cur = king;
        vector<string> ans;
        if(isDeath[king] == false) ans.push_back(king);
        Successor(cur, ans);
        return ans;
    }
};

1601.最多可达成的换楼请求数目 #枚举子集 #回溯+剪枝

题目链接

题意

$n $栋楼，编号从 (0) 到 (n - 1) 。每栋楼有若干员工。部分员工想换一栋楼居住。给定数组(requests(requests.size()leq16)) ，其中$ requests[i] = [from_i, to_i]$ ，表示一个员工请求从编号为 (from_i) 的楼搬到编号为 (to_i) 的楼。

一开始所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足每栋楼员工净变化为(0) 。意思是每栋楼离开的员工数目等于该楼搬入的员工数数目。比方说 (n = 3) 且两个员工要离开楼 (0) ，一个员工要离开楼 (1) ，一个员工要离开楼 2 ，如果该请求列表可行，应该要有两个员工搬入楼 (0) ，一个员工搬入楼 (1) ，一个员工搬入楼$ 2$ 。

请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。

分析

Solution1 : 枚举子集

由于(requests)数组最大长度为(16)，即总共有(16)条边，那么我们可以枚举选中某些边、不选某些边，共有(1<<16 = 65536)，由此计算出所有楼的度数是否为(0)，若为(0)说明入度等于出度，满足题意，更新最值；若不为(0)，则不可行。接下来我们将所有边的选择状态用一二进制去记录，然后枚举这个二进制数，内层再枚举该二进制数的子集即可。时间略慢，约(440ms)

class Solution {
public:
    int maximumRequests(int n, vector<vector<int>>& requests) {
        int ans = -1;
        int mymax = requests.size();
        for (int state = 0; state < (1 << mymax); state++){ //枚举状态
            int inD[22] = {0}, outD[22] = {0};
            int cnt = 0;
            for(int j = 0; j < mymax; j++){ //枚举子集
                if(state & (1 << j)){
                    outD[requests[j][0]]++;
                    inD[requests[j][1]]++;
                    cnt++;
                }
            }
            bool f = true;
            for (int i = 0; i < n; i++){
                if(inD[i] != outD[i]) {
                    f = false;
                    break;
                }
            }
            if(f) ans = max(ans, cnt);
        }
        return ans;
    }
};

Solution2 : 深搜回溯+剪枝

时间为(84ms)

class Solution {
private:
    int degree[20];
    int ans = -1;
public:
    void DFS(int start, vector<vector<int>>& requests, int sum, int n){
        if(start == requests.size()){
            for (int i = 0; i < n; i++)
                if(degree[i] != 0) return;
            ans = max(sum, ans);
        }
        else if((int)requests.size() - start + 1 + sum < ans) //常见剪枝方式
            return;
        else {
            DFS(start + 1, requests, sum, n); //不选第start条边
            degree[requests[start][0]]--;
            degree[requests[start][1]]++;
            DFS(start + 1, requests, sum + 1, n); //选中第start条边
            degree[requests[start][0]]++;
            degree[requests[start][1]]--;
        }
    }
    int maximumRequests(int n, vector<vector<int>>& requests) {
        DFS(0, requests, 0, n);
        return ans;
    }
};