贪心思路:
将牛按照最小spfa值排序, 然后从最大到最小枚举每个牛, 如果能找到防晒霜可以,则涂防晒。
这里从大到小的原因 :
二分图匈牙利证明方法。。我就不管了,看y神视频,我记下来过程先不管了
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
ll c, l;
pair<ll, ll> cows[maxn];
map<ll, ll> sp;
int main()
{
cin >> c >> l;
for(int i = 1; i <= c; i ++)
{
ll x,y;
cin >> x >> y;
cows[i] = {x,y}; // xiao da
}
for(int i = 1; i <= l; i ++)
{
ll x, y;
cin >> x >> y;
sp[x] += y;
}
sort(cows+1, cows+1+c);
ll ans = 0;
sp[0] = sp[1001] = c;
for(int i = c; i >= 1; i --)
{
auto cow = cows[i];
auto it = sp.upper_bound(cow.second); //找到大于等于牛最大防晒的最小防晒霜,然后减一就是可以包含的最大, 这里值得多记
it --;
if(it->first >= cow.first && it->first <= cow.second)
{
ans ++;
it->second --;
if(it->second == 0)
{
sp.erase(it);
}
}
}
cout << ans << endl;
return 0;
}