本题使用map函数(它自动去重)
map< int, int > spfs;,这里使用方法也比较独特,
定义spfa, 想加入两个数是这样加的spfa[a] += b
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int, int> PII;
const int N = 2510;
int n, m;
PII cows[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
cin >> cows[i].first >> cows[i].second;
//整体排序
sort(cows, cows + n);
map<int, int> spfs;//坐标,数量
for (int i = 0; i < m; i ++ )
{
int spf, cover;
cin >> spf >> cover;
//输入进map
spfs[spf] += cover;
}
//从后往前枚举,每个都使用尽可能偏大的数来应付牛,这样物尽其用,争取更多的牛涂到
int res = 0;
spfs[0] = spfs[1001] = n;
for (int i = n - 1; i >= 0; i -- )
{
auto cow = cows[i];
//upper_bound的意思是找到比它大的第一个数
auto it = spfs.upper_bound(cow.second);
//在--,再判断是否可以是区间内的数
it --;
if (it->first >= cow.first && it->first <= cow.second)
{
res ++;
if (-- it->second == 0)
spfs.erase(it);
}
}
cout << res;
}