AcWing 110. 防晒
原题链接
简单
作者:
烟花易冷
,
2020-08-11 20:34:03
,
所有人可见
,
阅读 807
代码就是yxc大佬的代码,我来贴个注释
// 贪心
//将所有奶牛按照 minSPF 从大到小的顺序排序,然后依次考虑每头奶牛;
//对于每头奶牛,扫描当前所有能用的防晒霜,选择 SPF 值最大的防晒霜来用;
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 2510;
int n, m, res = 0;
PII cows[N];
map<int, int> spfs;
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
cin >> cows[i].first >> cows[i].second;// n头牛的minSPF值和maxSPF值
for (int i = 0; i < m; i ++ )
{
int spf, cover;
cin >> spf >> cover;// 防晒霜的spf值和数量
spfs[spf] += cover; // spf值可能相同
}
sort(cows, cows + n);// 将所有奶牛按照 minSPF 从小到大的顺序排序
spfs[0] = spfs[1001] = n;// 哨兵
for (int i = n - 1; i >= 0; i -- )// 倒序(拨正排序)
{
auto spf = spfs.upper_bound(cows[i].second);// 大于第i头牛的maxSPF的最小元素
spf --;// spf--即为小于等于第i头牛的maxSPF值的最大元素
if (spf -> first >= cows[i].first)// 如果spf值大于第i头牛的minSPF值
{
res ++ ;// 发放防晒霜
if (--spf -> second == 0)// 数量为零,删除防晒霜名字
spfs.erase(spf);
}
}
cout << res << endl;
return 0;
}
能请问一下为什么要哨兵节点吗?