编程题
1
下面我们都将会有题目的截图来代替文字描述 如果大家想要查看题目的文字描述的话可以点击题目超链接进入
知识点：优先级队列的使用
具体的知识点可以参考我的这篇博客
我们使用优先级队列可以很轻松的解决topk问题
解析：本题其实并没有涉及什么算法 更多的难点是思维上的
题目要求我们要将每个队伍中的第二水平高的人相加起来最大
所以说数值最大的人是永远不可能被选上的 因为他肯定不是水平第二高的（第一第二水平相同例外）
那么我们要发挥他的最大用处 就可以让他带一个水平第二高的和一个水平最低的人参赛
那么这就是第一个队伍
第二个队伍以此类推
那么我们很简单就能推出第二个队员的最大水平值 就是水平第二高的
第二个队员的第二大水平值就是水平第四高的
… …以此类推
反应到我们的优先级队列上就是先pop一个最大的 接下来的值就是我们想要的
代码解决方案如下
#include <iostream> using namespace std; #include <queue> int main() { int k = 0; cin >> k; priority_queue<int> pq1; int m = 0; while(cin >> m) { pq1.push(m); } long long sum = 0; vector<int> v; while(k--) { pq1.pop(); v.push_back(pq1.top()); pq1.pop(); } for (auto x : v) { sum += x; } cout << sum; return 0; }
2
知识点：哈希表的使用
具体的知识点可以参考我的这篇博客
其实一般遇到这种删除的题目我们第一时间就应该想到使用哈希表来简化查找（因为哈希表的查找效率是O(1)）
解析：这个题目中我们只需要知道key值存不存在就好了 并不需要知道其他信息所以说使用set就好了
之后我们只需要遍历需要删除的字符串 查找该字符是否要删除 如果不要就加入到新字符串中
思路很简单
代码中还有一个需要注意的点 我们如果使用cin接受字符串的话 遇到空格就会终止
所以说这里我们不能使用cin 必须要使用getline函数接受一句话
参考博客如下
代码表示如下
#include <iostream> #include <unordered_map> using namespace std; #include <string> #include <unordered_set> int main() { string s1; string tok; getline(cin,s1); // 因为有空格 所以说必须要用getline cin >> tok ; unordered_set<char> set; for (auto x : tok) { set.insert(x); } string ans; for (auto x : s1) { if (set.find(x) == set.end()) { ans += x; } } cout << ans; return 0; }
