Acwing 周赛135 解题报告 | 珂学家

本文主要是介绍Acwing 周赛135 解题报告 | 珂学家 | 反悔堆贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

在这里插入图片描述

整体评价

VP了这场比赛， T3挺有意思的，反悔贪心其实蛮套路的。

A. 买苹果

思路: 签到

n, x = list(map(int, input().split()))
print (n // x)

B. 牛群

思路: 分类讨论

from collections import Counters = input()
cnt = Counter(s)lists = sorted(cnt.values())n = len(lists)
if n >= 5:print ("No")
elif n == 4:print ("Yes")
elif n == 3:mz = lists[-1]if mz >= 2:print("Yes")else:print("No")
elif n == 2:if lists[0] >= 2 and lists[1] >= 2:print("Yes")else:print("No")
else:print("No")

C. 货运公司

思路: 反悔堆

类似这种1vs1匹配，有限制，又求最大收益的题，往往是反悔堆解法。

当然也可以用网络流，但是反悔的思路更常见。

这种思路，也属于贪心中的，很特别的存在，有一定的套路在。


#include <bits/stdc++.h>using namespace std;struct T1 {int p, w, idx;bool operator< (const T1 &other) {return this->p < other.p;}
};struct T2 {int p, idx;bool operator< (const T2 &other) {return this->p < other.p;}
};struct T3 {int w, idx1, idx2;
};struct T3Comp {bool operator() (const T3 &lhs, const T3 &rhs) const {return lhs.w > rhs.w;}
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);int n;cin >> n;vector<T1> vi;for (int i = 0; i < n; i++) {int p, w;cin >> p >> w;vi.push_back({p, w, i + 1});}std::sort(vi.rbegin(), vi.rend());int m;cin >> m;vector<T2> arr(m);for (int i = 0; i < m; i++) {cin >> arr[i].p;arr[i].idx = i + 1;}std::sort(arr.rbegin(), arr.rend());priority_queue<T3, vector<T3>, T3Comp> pq;long long res = 0;int j = 0;for (int i = 0; i < n; i++) {if (j < m && vi[i].p <= arr[j].p) {pq.push({vi[i].w, vi[i].idx, arr[j].idx});res += vi[i].w;j++;} else {if (!pq.empty() && vi[i].w > pq.top().w) {auto item = pq.top();res -= item.w;pq.pop();res += vi[i].w;pq.push({vi[i].w, vi[i].idx, item.idx2});}}}cout << pq.size() << " " << res << endl;while (!pq.empty()) {auto item = pq.top();pq.pop();cout << item.idx1 << " " << item.idx2 << endl;}return 0;
}