匈牙利算法， 贪心

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
typedef pair<int,int> PII;
PII ma[maxn], te[maxn];  //由于要有x和y排序，用pair比struct方便
int n, m;

int main()
{
    while(cin >> n >> m)
    {
        for(int i = 0; i < n; i ++) cin >> ma[i].first >> ma[i].second;
        for(int i = 0; i < m; i ++) cin >> te[i].first >> te[i].second;

        sort(ma ,ma + n);
        sort(te ,te + m);

        multiset<int> se; //就是set不删除重复元素
        ll ans = 0;
        ll mul = 0;
        for(int i = m-1,j = n-1; i >= 0; i --)
        {
            int x = te[i].first;
            int y = te[i].second;
            while(j >= 0 && ma[j].first >= x) //如果当前机器x值大于要找的x并且枚举所有的机器
            {
                se.insert(ma[j--].second);    //将当前的y值存入，因为我们要找大于任务y的最小的机器的y
            }
            auto it = se.lower_bound(y);      //用二分查找大于任务y的最小的机器y
            if(it != se.end())              //如果等于end（）则是不存在这样的数
            {
                ans ++;         //次数加
                mul += 500*x+2*y;  //价值加
                se.erase(it);   //一定要记得用了机器要删除掉当前机器
            }
        }
        cout << ans <<' ' << mul << endl;
    }
    return 0;
}