前言
整体评价
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;
}
