【华为OD：C++机试】Day

华为OD：C++机试】Day"/>

【华为OD：C++机试】Day

目录

🌷1. 排队游戏：

🌷2. 购物：

🌷3. 划分字符串：

🌷4. MELON 的难题：

🌷5. 荒岛求生：

🌷6. 通过软盘拷贝文件：

🌷7. 数字序列比大小：

🌷8. 树状结构查询：

🌷9. 评论转换输出：

🌷10. 找出两个整数数组中同时出现的整数：

---

🌷1. 排队游戏：

题目描述：

code： 

// 排队游戏
#include <iostream>
#include <vector>
#include <unordered_set>using namespace std;int sum(const vector<int>& capacity, int n)
{int count = 0;for (int i = 0; i < n; i++)if (capacity[i] > capacity[n])count++;return count;
}int main()
{int n, m, k;cin >> n >> m >> k;// 用于存储刺头学生位置unordered_set<int> set;for (int i = 0; i < m; i++){int num;cin >> num;set.insert(num);}// 用于存储学生的能力值vector<int> capacity(n);for (int i = 0; i < n; i++){cin >> capacity[i];}int ans = 0;for (int i = 0; i < n; i++){if (!set.count(i))ans += sum(capacity, i);}if (ans > k)cout << 1 << endl;elsecout << 0 << endl;return 0;
}

🌷2. 购物：

题目描述：

code： 

// 购物
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<vector<int>> result;
vector<int> path;void backTracking(vector<int>& price, int startindex, vector<bool>& used)
{result.push_back(path);for (int i = startindex; i < price.size(); i++){// 如果要去重的话，则要加上下面的语句 和 used语句//if (i > 0 && price[i] == price[i - 1] && used[i-1] == false) continue;path.push_back(price[i]);//used[i] = true;backTracking(price, i + 1, used);path.pop_back();//used[i] = false;}
}int main()
{// 分别读入：物品的个数 和 总价钱int n, k;cin >> n >> k;vector<bool> used(n, false);// 读入各个物品的价格vector<int> price(n);for (auto& e : price)cin >> e;// 将上面数组中所有的子集存放到result数组中backTracking(price, 0, used);// ans数组存放各子集的和vector<int> ans;for (const auto& s : result){int sum = 0;for (const auto& e : s)sum += e;ans.push_back(sum);}sort(ans.begin(), ans.end());for (int i = 1; i <= k; i++)cout << ans[i] << endl;return 0;
}

🌷3. 划分字符串：

题目描述：

code： 

// 划分字符串
#include <iostream>
#include <string>
#include <vector>using namespace std;int left_sum(const vector<int>& save, int k)
{int sum = 0;for (int i = 0; i < k; i++)sum += save[i];return sum;
}int right_sum(const vector<int>& save, int j)
{int sum = 0;for (int i = j + 1; i < save.size(); i++)sum += save[i];return sum;
}vector<int> find_value(const string& str)
{// 判断字符串的不合法性if (str.size() < 5 || str.size() > 30)return { 0, 0 };// 将字符串转换为数字存储在数组中vector<int> save;for (auto& e : str)save.push_back(static_cast<int>(e));// 求出数组中的所有元素的和int sum = 0;for (const auto& e : save)sum += e;for (int i = 1; i < save.size() - 1; i++){int target = save.size() - 2;while (i < target){int left = left_sum(save, i);int right = right_sum(save, target);int mid_sum = sum - left - right - save[i] - save[target];if (left == right && left == mid_sum)return { i, target };target--;}}return { 0,0 };
}int main()
{// 用于存储输入的字符串string str;cin >> str;vector<int> index = find_value(str);cout << index[0] << ',' << index[1] << endl;return 0;
}

🌷4. MELON 的难题：

题目描述：

code： 

// MELON的难题
#include <iostream>
#include <vector>using namespace std;int half = 0;
int min_count = INT_MAX;void solve_method(const vector<int>& save, int count, vector<int>& lst, int index)
{if (count == half){if (index < min_count)min_count = index;if (save.size() - index < min_count)min_count = save.size() - index;}else{for (int i = index; i < save.size(); i++){lst[index] = save[i];count += lst[index];if(count <= half && ( index < min_count || save.size() - index < min_count))solve_method(save, count, lst, index + 1);count -= lst[index];}}
}int main()
{int n;cin >> n;// 将雨花石的重量存在数组中vector<int> save(n);for (auto& e : save)cin >> e;// 求出雨花石的重量总和int sum = 0;for (const auto& e : save)sum += e;// 判断雨花石的重量是否可以整除2if (sum % 2 != 0)cout << -1 << endl;else{half = sum / 2;vector<int> lst(n);solve_method(save, 0, lst, 0);cout << min_count << endl;}return 0;
}

🌷5. 荒岛求生：

题目描述：

code： 

// 荒岛求生
#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <sstream>using namespace std;vector<int> exchange(const string& str)
{stringstream ss(str);string s;vector<int> save;while (getline(ss, s, ' '))save.push_back(stoi(s));return save;
}int main()
{string str;getline(cin, str);vector<int> save = exchange(str);stack<int> st;int i = 1;int count = 0;st.push(save[0]);while (i < save.size()){if ((save[i - 1] < 0 && save[i] < 0) || (save[i - 1] > 0 && save[i] > 0))st.push(save[i++]);else{int top = st.top();st.pop();int c = top + save[i];if (c != 0){if (c > 0 && top > 0){count++;st.push(c);}else{count--;save[i] = c;}}else{save.erase(save.begin() + i);}}}cout << count + st.size() << endl;return 0;
}

🌷6. 通过软盘拷贝文件：

题目描述：

code： 

// 通过软件拷贝文件
#include <iostream>
#include <vector>using namespace std;int bag = 1474560 / 512;int main()
{int n;cin >> n;// 存储文件的容量vector<int> cap(n);for (auto& e : cap)cin >> e;// 存储文件所占的块数vector<int> wei(n);for (int i = 0; i < n; i++){if (cap[i] % 512 == 0)wei[i] = cap[i] / 512;elsewei[i] = cap[i] / 512 + 1;}// 动态规划数组记录背包容量下的最大价值vector<int> dp(bag + 1, 0);for (int i = 0; i < n; i++){for (int j = bag; j >= wei[i]; j--)dp[j] = max(dp[j], dp[j - wei[i]] + cap[i]);}// 输出最大值cout << dp[bag] << endl;return 0;
}

🌷7. 数字序列比大小：

题目描述：

code： 

// 数字序列比大小
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main()
{int n;cin >> n;vector<int> a(n);vector<int> b(n);for (auto& e : a)cin >> e;cin.ignore();for (auto& e : b)cin >> e;sort(a.begin(), a.end());sort(b.begin(), b.end());int ans = 0;for (int i = 0; i < n; i++){int num = a[i];if (num < b[0]){ans--;b.pop_back();}else{if (num > b[0])ans++;b.erase(b.begin());}}cout << ans << endl;return 0;
}

🌷8. 树状结构查询：

题目描述：

code： 

// 树状结构查询
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>using namespace std;int main()
{// 总共有多少行数据int n;cin >> n;// 以树状形式存储数据map<char, vector<char>> tree;for (int i = 0; i < n; i++){char a, b;cin >> a >> b;tree[b].push_back(a);}// 要求的父节点char parent;cin >> parent;vector<char> child = tree[parent];vector<char> ans;while (!child.empty()){char c = child[0];child.erase(child.begin());ans.push_back(c);if (tree.count(c)){for (const auto& e : tree[c])child.push_back(e);}}sort(ans.begin(), ans.end());for (const auto& e : ans)cout << e << endl;return 0;
}

🌷9. 评论转换输出：

题目描述：

code： 

// 评论转换输出
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <list>using namespace std;list<string> exchange(const string& str)
{stringstream ss(str);string s;list<string> lst;while (getline(ss, s, ','))lst.push_back(s);return lst;
}void ensure_level_exists(vector<vector<string>>& tree, int level)
{if (tree.size() < level)tree.push_back(vector<string>());
}void recursive(list <string>& lst, int childCount, vector<vector<string>>& tree, int level)
{for (int i = 0; i < childCount; i++){string comment = lst.front();lst.pop_front();ensure_level_exists(tree, level);tree[level - 1].push_back(comment);int child = stoi(lst.front());lst.pop_front();if (child > 0)recursive(lst, child, tree, level + 1);}
}void printTree(vector<vector<string>>& tree)
{cout << tree.size() << endl;for (const auto& e : tree){for (const auto& c : e){cout << c << " ";}cout << endl;}
}int main()
{// 用于存储输入的字符串string str;cin >> str;// 将字符串转换为数组进行存储list<string> lst = exchange(str);// 将数据以数的形式进行存储vector<vector<string>> tree;int level = 1;while (!lst.empty()){string comment = lst.front();lst.pop_front();ensure_level_exists(tree, level);tree[level - 1].push_back(comment);int child = stoi(lst.front());lst.pop_front();recursive(lst, child, tree, level + 1);}printTree(tree);return 0;
}

🌷10. 找出两个整数数组中同时出现的整数：

题目描述：

code： 

// 找出两个整数数组中同时出现的整数
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <unordered_map>
#include <map>
#include <algorithm>using namespace std;vector<int> exchange(const string& str)
{stringstream ss(str);string s;vector<int> save;while (getline(ss, s, ','))save.push_back(stoi(s));return save;
}int main()
{string str1, str2;cin >> str1 >> str2;vector<int> a = exchange(str1);vector<int> b = exchange(str2);unordered_map<int, int> map1;unordered_map<int, int> map2;for (const auto& e : a)map1[e]++;for (const auto& e : b)map2[e]++;map<int, vector<int>> map;for (const auto& e : map1){int num = e.first;int count = e.second;if (map2.count(num)){int n = min(count, map2[num]);map[n].push_back(num);}}if (map.empty())cout << "NULL" << endl;else{for (const auto& e : map){int num = e.first;vector<int> cap = e.second;sort(cap.begin(), cap.end());cout << num << ":";for (int i = 0; i < cap.size(); i++){if (i != cap.size() - 1)cout << cap[i] << ',';elsecout << cap[i] << endl;}}}return 0;
}

坚持打卡！😃