9.11日机考
1. 均衡的任务调度
机房运行了K个计算节点，每个节点当前负载数为T，每个节点的CPU核心数为C，一个CPU核心的最大负载数为200，节点总负载数=节点CPU核心数*200，节点的CPU负载=节点当前负载数/节点负载总数。节点宕机在机房是经常发生的事，因此要设计一种算法将宕机节点的负载均衡地迁移到负载低的节点，使各节点的CPU负载保持一致，给定宕机节点的负载数N，求每个计算节点应新增的负载数。
备注：
- 如果宕机节点的负载数超过了所有节点的总负载数，不进行重新调度，则每个节点新增的任务数为0；
- 如果宕机节点的负载数没有超过所有节点总负载数，输入能够保证最终分配完全平衡，即分配后各个计算节点的CPU负载保持相等，精度不低于0.001.
输入
- 宕机节点的负载数N
- 计算节点的台数K
- 每个节点的核心数C
- 每个节点当前的负载数T
输出
每个节点应该新增的负载数。
样例
输入：1180
3
45 28 45
6750 4200 6750
输出：450 280 450
解释：宕机节点有1180个负载待转移，计算节点有3个，CPU核心数分别为45，28，45，当前负载分别为6750，4200，
6750。
三个节点分别迁移450，280，450个负载后，节点的CPU负载分别为(450+6750)/(45*200)=0.8,
(280+4200)/(28*200)=0.8, (450+6750)/(45*200)=0.8，所以返回了450 280 450。
解答
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(k), b(k);
for (int &t : a) {
cin >> t;
}
for (int &t : b) {
cin >> t;
}
int available = 0, cpu = 0, cur_load = 0;
for (int i = 0; i < k; ++i) {
available += a[i] * 200 - b[i];
cpu += a[i];
cur_load += b[i];
}
if (n > available) {
for (int i = 0; i < k; ++i) {
if (i != 0) cout << " ";
cout << 0;
}
}
int load_factor = (cur_load + n) / cpu;
for (int i = 0; i < k; ++i) {
if (i != 0) cout << " ";
cout << load_factor * a[i] - b[i];
}
}
2. 切换工作目录
Linux系统中，绝对路径是从根目录开始的完整路径，即以‘/’开头，相对路径是从当前工作目录开始的路径，以‘.’、‘..’或当前目录的子目录名开始。某用户使用‘cd’相对路径的指令来切换工作目录，假设其使用的相对路径包含如下部分：
- 一个点'.'表示当前目录；
- 两个点‘..’表示上一级目录，根目录的上一级仍然是根目录；
- 斜杠'/'用于分割目录，连续的多个斜杠等价于单个斜杠；
- 其他字符串均代表目录名，如‘...’、‘hello’，且假设目录都存在；
请计算出用户在使用'cd'相对路径指令后的工作目录，要求：
- 以绝对路径的形式输出，即以‘/’开始；
- 以最简洁形式输出；最简洁形式指的是路径中没有冗余部分，即没有'.'，‘..’、‘//’，不以‘/‘结尾；
另外，假设cd指令执行过程中，会依次进入每一级目录，请给出，经过的最深的目录的层级数，包括当前目录和最终目录，假设根目录'/'为0层。
输入
第一行为当前工作目录的绝对路径，为最简洁形式；字符数范围[1, 100]；
第二行为用户执行的cd相对路径命令，cd和相对路径之间有一个空格隔开，相对路径的字符数范围为[1, 100]，注意cd和空格还有3个字符；
输出
第一行为用户执行完'cd相对路径'指令后的当前工作目录，要求以最简洁的绝对路径形式输出。
第二行为中执行过程中经过的最深目录层级数。
样例
输入：/home/hello
cd .././/world/
输出：/home/world
2
解释：指令执行过程中进入的目录依次为：/home/hello、/home、/home/world，最终目录为/home/world，深度层级为2.
解答
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> input() {
string s;
getline(cin, s);
s += '/';
vector<string> res;
string t;
for (char c : s) {
if (c == '/') {
if (t.size()) res.push_back(t);
t = "";
} else {
t += c;
}
}
return res;
}
int main() {
vector<string> a = input();
cin.get();
cin.get();
cin.get();
vector<string> b = input();
int deep = a.size();
for (string& s : b) {
if (s == ".") continue;
if (s == "..") {
if (a.size()) a.pop();
} else {
a.push_back(s);
}
deep = max(deep, (int)a.size());
}
for (string s : a) cout << "/" << s;
if (a.empty()) cout << "/";
cout << endl << deep << endl;
}
3. 网络总带宽
有n台交换机设备，用于搭建并行计算接入网络，给定长度为n的两个整数数组port和bandwidth，port[i]代表第i台交换机的端口数量，bandwidth[i]表示第i台交换机单个端口的带宽（假设同一台交换机设备上各个端口的带宽相同），需要从这n台交换机中选择最多k台（可以小于k）不同的交换机，使其组成的网络带宽最大，整个网络总带宽定义为所选交换机的端口数量乘以所选交换机的中端口带宽的最小值，请你反悔最多k台不同交换机的网络总贷款的最大值。
输入
- 第一行的输入是一个整数n，表示交换机的数量1<=n<=100；
- 第二行的输入是一个长度为n的整数数组port，表示n台交换机的端口数量，port[i]表示第i台交换机的端口数量，20<=port[i]<=100；
- 第三行输入是一个长度为n的整数数组bandwidth，表示n台交换机的端口带宽，bandwidth[i]代表i台交换机的端口带宽，bandwidth[i]代表第i台交换机端口带宽，10<bandwidth[i]<=100；
- 第四行输入是一个整数k，表示可与选择的不同交换机数量，1<=k<=n
输出
一个整数，即最多k台交换机的网络总带宽最大值
样例
输入：6
20 100 30 10 50 80
50 40 30 90 70 20
2
输出：6000
解释：从6台交换机中最多选择出2台交换机，选择下标为1（端口数量为：100，带宽为：40），下标为4（端口数量为50，带
宽为：70）的两台交换机，则总带宽为最大（100+50）*min(40, 70)=6000
解答
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k;
cin >> n;
vector<pair<int, int>> v(n);
for (int i = 0; i < n; ++i) {
cin >> v[i].second;
}
for (int i = 0; i < n; ++i) {
cin >> v[i].first;
}
sort(v.begin(), v.end());
int ans = 0;
for (int i = 0; i < n; ++i) {
multiset<int> s;
for (int j = i; j < n; ++j) {
s.insert(v.second);
if (s.size() > k) s.erase(s.begin());
}
int cnt = 0;
for (int t : s) cnt += t;
ans = max(ans, v[i].first * cnt);
}
cout << ans << endl;
}
