华为11.08笔试题目
第一题、消息配对
给定n个进程,每个进程拥有一个消息序列,现在要求对不同进程之间的消息进行配对,输出完成配对的消息总数量。规则如下:
- 单个消息表示为
si
或ri
,其中si
表示发送消息给目标进程i
,r
表示从目标进程i接收消息,其中0 <= i < n
。 - 第
i
个进程的消息sj
和第j
个进程的消息ri
可以完成配对,其中(j != i)
。 - 如果某个进程中的第
i
个消息未完成匹配,则该进程的第j (j > i)
个消息不能参与匹配。
输入
n以及n个消息序列,具体格式如下 第1行:n,表示总进程数 第2行:进程0的消息序列,消息之间采用空格分隔 第3行:进程1的消息序列,消息之间采用空格分隔 ... 第n+1行:进程n-1的消息序列,消息之间采用空格分隔
输出
完成配对的消息总数量
例子
2 s1 r1 s1 r1 s1 r0 s0 s0 s0 r0 输出4 4 s1 s2 s3 s0 s2 s3 r0 r1 r0 r1 输出0 4 s1 r3 r0 s2 r1 s3 r2 s0 输出8
题解
没参加这场机考,自己写的答案不确定对不对,能通过上面三个例子。
#include <iostream> #include <vector> #include <string> #include <sstream> #include <unordered_map> #include <queue> int main() { int n; std::cin >> n; // 每个进程的发送消息队列,bool为true表示发出,false表示接收 std::vector<std::queue<std::pair<bool, int>>> queues(n); // 读取每个进程的消息序列 std::string line; std::cin.ignore(); // 忽略之前的换行 for (int i = 0; i < n; ++i) { std::getline(std::cin, line); std::istringstream stream(line); std::string msg; while (stream >> msg) { if (msg[0] == 's') { queues[i].emplace(true, std::stoi(msg.substr(1))); } else { queues[i].emplace(false, std::stoi(msg.substr(1))); } } } int matchedPairs = 0; bool cond = true; while (cond) { cond = false; for (int i = 0; i < n; ++i) { if (queues[i].empty()) { continue; } int sendTo = queues[i].front().second; if (queues[i].front().first && !queues[sendTo].front().first && (queues[sendTo].front().second == i)) { queues[i].pop(); queues[sendTo].pop(); matchedPairs += 2; cond = true; } } } std::cout << matchedPairs << std::endl; return 0; }
第三题、最少费用的可达路线
随着疫情放开,小明准备自驾旅行,旅行中经过的每个城市都有一些朋友需要去探访消费,最近小明有点经济紧张,情帮小明设计一下行驶路线,能用最少的探访费用到达终点。
1、小明的汽车是电车,最多只能行驶M公里,目中间城市没有充电桩
2、 假如旅行一共有N个城市,城市序号分别为0, 1, 2,。。, N-1,则起点为0,终点为N-1
3、 每个城市游玩需要费用为fees = [f0, f1, f2, f3..],每项费用f>=0,总费用包括fees[0]和fees[N-1]
4、每两个城市之间耗电通过(i, j, k) 标识从i到j或者从j到i是可以相互到达的,并且需要耗电k公里,未定义的视为不可到达
输入
第一行:汽车最大可行驶距离M (0< M <= 1000) 第二行:城市数量N (1 < N <= 1000),及每个城市的消费费用 第三行:城市间联通关系数量K 后续K行: i j k表示i到j或者j到i需要耗电k公里
输出
可达:输出最少的探访费用 不可达,输出-1
例子
500 4 1000 3000 4000 2000 5 0 1 200 0 3 250 1 3 300 0 2 150 2 3 250 输出:3000 解释:最优路径为0->3,总共需要耗电250公里,需要支付费用3000 400 4 1000 3000 4000 2000 4 0 1 200 1 3 300 0 2 150 2 3 250 输出: 7000 解释:最优路径为 0-> 2 -> 3,总共需要耗电380公里,需要支付费用7000
题解
思路是dijkstra's algorithm
priority_queue中城市的优先级为:花费越低、剩余电量越高,优先级越高。
#include <queue> #include <algorithm> #include <iostream> using namespace std; int m, n, k; priority_queue<pair<pair<int, int>, int>> q; int main() { cin >> m >> n; vector<int> fees(n); for (int i = 0; i < n; i++) cin >> fees[i]; vector<vector<int>> e(n, vector<int>(n, INT_MAX)); // Edges cin >> k; while (k--) { int x, y, v; cin >> x >> y >> v; e[x][y] = e[y][x] = min(e[x][y], v); } vector<vector<int>> dp(n, vector<int>(m + 1, INT_MAX)); dp[0][m] = fees[0]; q.push({ {-fees[0], m}, 0 }); while (q.size()) { auto t = q.top(); q.pop(); int f = -t.first.first; // 当前花费 int y = t.first.second; // 当前电量 int cur = t.second; // 当前城市 if (f > dp[cur][y]) continue; // Overestimated Node for (int i = 0; i < n; i++) { if (i == cur) continue; int ty = y - e[cur][i], tf = f + fees[i]; if (ty <= 0 || tf >= dp[i][ty]) continue; dp[i][ty] = tf; q.push({ {-tf, ty}, i }); } } int ans = *min_element(&dp[n - 1][0], &dp[n - 1][m]); if (ans < 1e7) { cout << ans << endl; } else { cout << -1 << endl; } return 0; }