【HDOJ 4864】Tack（贪心）

题面：Tack

题目大意

今天某公司有 $m$ 个任务需要完成。 每个任务都有自己相应的难度级别和完成任务所需的时间，记作 $(y,x)$。 公司若完成第 $i$ 个任务，可以获得 $(500\ast x_i+2\ast y_i)$ 美元的报酬。 现在，公司有 $n$ 台机器，每台机器都有相应的最长工作时间和级别。 如果任务所需时间超过机器的最长工作时间，则机器无法完成此任务。 如果任务难度级别超过机器的级别，则机器无法完成次任务。 每台机器一天内只能完成一项任务。 每个任务只能由一台机器完成。 请为他们设计一个任务的分配方案，使得公司能够最大化他们今天的任务完成数量。 若有多种解决方案，请选择报酬最高的一项。

思路

分析题目，可以发现题目要我们解决这样两个问题：

任务的最大匹配问题匹配结果要使总价值最大

分析这两个问题，可以看出我们要解决的就是一个点权二分图最大匹配的问题。那么这道题就只要用一下匈牙利算法和贪心的思想就行了。

贪心思想

分析题目，发现 $0\le x_i\le 1440$，$0\le y_i\le 100$，而每一项任务的价值是 $500\ast x+2\ast y$，我们可以看出，$x$每多一个单位，$y$无论取任何值都是不会大过 $x+1$ 后的价值。

所以我们要优先考虑 $x$。

当我们按优先 $x$ ，后 $y$，从小到大排好序后。 我们要从任务的最后一项开始往前遍历，这样是为了使得最终总价值最大。 之后，将所有最长工作时间大于当前任务所需的时间的机器放入一个集合。再考虑要用哪一个机器来解决当前这个任务。

假设有多个机器符合条件，那么我们应该找到级别比当前任务的难度级别还大的第一个机器，这样我们可以留下级别更高的机器去解决剩下的任务，因为级别更高的机器可以进行匹配的任务相对也会更多。或者说，我们应该用最小的代价去解决每一个任务。

代码

#include <bits/stdc++.h> #define sc scanf #define pf printf using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 1e5 + 10; int n, m; PII mchs[N], tacks[N]; int main() { while(cin >> n >> m) { for(int i = 0; i < n; i++) cin >> mchs[i].first >> mchs[i].second; for(int i = 0; i < m; i++) cin >> tacks[i].first >> tacks[i].second; sort(mchs, mchs + n); sort(tacks, tacks + m); LL ans = 0, cnt = 0; multiset<int> yst; for(int i = m - 1, j = n - 1; i >= 0; i--) { int x = tacks[i].first, y = tacks[i].second; while(j >= 0 && mchs[j].first >= x) yst.insert(mchs[j--].second); auto k = yst.lower_bound(y); if(k == yst.end()) continue; cnt ++; ans += 500 * x + 2 * y; //一台机器只能匹配一个任务 yst.erase(k); } cout << cnt << " " << ans << endl; } return 0; }