本周周赛的题面风格与以往不太一样，但不要被吓着，读懂题意跟着模拟，其实会发现并不会难到哪里去。
1599. 经营摩天轮的最大利润 #模拟
题意
摩天轮4个座舱，每个座舱最多可容纳4位游客，座舱会轮转，且每次轮转需支付一定运行成本runningCost，且恰好转动1/4周。
给定长度为n的数组customers，customers[i] 是在第i 次轮转之前到达的新游客的数量，即你必须在新游客到来前轮转i 次。每位游客在登上离地面最近的座舱前都会支付登舱成本boardingCost ，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。注意，如果有超过 4 位游客在等摩天轮，那么只有 恰好4 位游客可以登上摩天轮，其余的需要等待 下一次轮转 。你需要返回最大化利润所需执行的 最小轮转次数 。 如果不存在利润为正的方案，则返回−1。
样例
分析
利用队列去模拟摩天轮的四个舱位，之所以用队列，是因为该四个舱位的出现存在顺序，先来的游客便先获得机会登上座舱。但注意，每个座舱不一定坐满乘客！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
private:
queue<int> motian;
public:
int minOperationsMaxProfit(vector<int>& customers, int boardingCost, int runningCost) {
int last = 0, cur = 0, bonus = 0;
int i = 0, ans = -0x3f3f3f3f, pos = -1;
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的向量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| const int MAXN = 1e5 + 5;
class ThroneInheritance {
private:
string king;
unordered_map<string, bool> isDeath;
unordered_map<string, vector<string>> Order;
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){
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()≤16) ，其中$ requests[i] = [from_i, to_i]$ ，表示一个员工请求从编号为fromi 的楼搬到编号为toi 的楼。
一开始所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为0 。意思是每栋楼离开的员工数目 等于 该楼 搬入的员工数数目。比方说n=3 且两个员工要离开楼0 ，一个员工要离开楼1 ，一个员工要离开楼 2 ，如果该请求列表可行，应该要有两个员工搬入楼0 ，一个员工搬入楼1 ，一个员工搬入楼$ 2$ 。
请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。
分析
Solution1 : 枚举子集
由于requests数组最大长度为16，即总共有16条边，那么我们可以枚举选中某些边、不选某些边，共有1<<16=65536，由此计算出所有楼的度数是否为0，若为0说明入度等于出度，满足题意，更新最值；若不为0，则不可行。接下来我们将所有边的选择状态用一二进制去记录，然后枚举这个二进制数，内层再枚举该二进制数的子集即可。时间略慢，约440ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| 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);
degree[requests[start][0]]--;
degree[requests[start][1]]++;
DFS(start + 1, requests, sum + 1, n);
degree[requests[start][0]]++;
degree[requests[start][1]]--;
}
}
int maximumRequests(int n, vector<vector<int>>& requests) {
DFS(0, requests, 0, n);
return ans;
}
};
|
