华为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;
}
美团一面802人在聊