Sunscreen
3222 ワード
题目:全部でC头の牛は日光浴をしなければなりません.i头の牛に必要な日差しの强さは区间[mini,maxi]の间にあります.日光は一部の牛にとって强すぎるので、一部の牛に日焼け止めクリームを涂る必要があります.質問最大何頭の牛に日焼け止めクリームを塗ることができますか?構想:乳牛を日光強度の最小値に従って小さいから大きいまで並べ替えて、日焼け止めクリームも日光強度によって小さいから大きいまで並べ替えます.乳牛が太陽光強度の最小値が日焼け止めクリームの太陽光強度より小さい必要がある場合、乳牛の太陽光強度の最大値を優先キューに入れる.乳牛の太陽光を必要とする最大強度値を、この日焼け止めクリームの太陽光強度と比較し、日焼け止めクリームの太陽光強度が乳牛の太陽光を必要とする強度の間に適切であればカウントする.
#include
#include
#include
#include
#include
#include
#include
#define MAXN 2505
using namespace std;
int C, L;
typedef pair<int, int> P;
priority_queue<int, vector<int>, greater<int> > q;
P cow[MAXN], bot[MAXN];
int main()
{
scanf("%d%d", &C, &L);
for(int i = 0; i < C; i++) {
scanf("%d%d", &cow[i].first, &cow[i].second);
}
for(int i = 0; i < L; i++) {
scanf("%d%d", &bot[i].first, &bot[i].second);
}
sort(cow, cow + C);
sort(bot, bot + L);
int j = 0, ans = 0;
for(int i = 0; i < L; i++)
{
while(j < C && cow[j].first <= bot[i].first)
{
q.push(cow[j].second);
j++;
}
while(!q.empty() && bot[i].second)
{
int x = q.top();
q.pop();
if(x < bot[i].first) continue;
ans++;
bot[i].second--;
}
}
printf("%d
", ans);
return 0;
}