贪心处理加优先队列
枚举每一个防嗮霜 对于其防嗮值找到与之最接近的奶牛防嗮左值,
并将其右值加入优先队列
处理队列中的值时,判断队列头的值是否小于当前防嗮值,如果是这说明这头牛防嗮不了
解释:每头牛的右值存储在小根堆维护的优先队列中,并且防嗮值排过序
如果当前防嗮霜没用,说明找不到合适的防嗮霜
#include<iostream>
#include<queue>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N = 2505;
typedef pair<int, int> PII;
PII spf[N], cow[N];
priority_queue<int, vector<int>, greater<int> > pq;
int n, m;
void readpii(PII& a)
{
cin >> a.x >> a.y;
return;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
readpii(cow[i]);
for (int i = 0; i < m; i++)
readpii(spf[i]);
sort(cow, cow + n);
sort(spf, spf + m);
int j = 0, cnt = 0;
for (int i = 0; i < m; i++)
{
while (j < n && cow[j].first <= spf[i].x)
{
pq.push(cow[j].y);
j++;
}
while (pq.size()&&spf[i].y)
{
int x = pq.top(); pq.pop();
if (spf[i].x > x)continue;
cnt++;
spf[i].y--;
}
}
cout << cnt << endl;
}