当前位置: 代码迷 >> 综合 >> POJ 3614 (贪心)
  详细解决方案

POJ 3614 (贪心)

热度:39   发布时间:2023-11-25 14:01:17.0

POJ 3614 (贪心)

原题链接

思路:把牛的最小值升序排序,防晒霜的防晒强度升序排序。如果牛最小承受小于防晒霜的,让牛的最大防晒进队。然后判断队列里面牛的最大承受大于防晒霜,就答案加1

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n, m;
struct node{int a, b;bool operator < (const node & a1) const{return a < a1.a;}
}cow[N], bot[N];
int main(){#ifdef ONLINE_JUDGE#elsefreopen("in.txt", "r", stdin);#endif // ONLINE_JUDGEint ans  = 0;scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){scanf("%d%d", &cow[i].a, &cow[i].b);}for(int i = 1; i <= m; i++){scanf("%d%d", &bot[i].a, &bot[i].b);}sort(cow + 1, cow + 1 + n);sort(bot + 1, bot + 1 + m);priority_queue<int, vector<int>, greater<int> > q;for(int i = 1, j = 1; i <= m; i++){while(j <= n && cow[j].a <= bot[i].a){q.push(cow[j].b);j++;}while(!q.empty() && bot[i].b){int t = q.top();q.pop();if(t < bot[i].a) continue;ans++;bot[i].b--;}}printf("%d\n", ans);return 0;
}

posted on 2019-04-02 16:51 坤sir 阅读(...) 评论(...) 编辑 收藏