首页 > 代码库 > POJ 3614 Sunscreen(贪心)
POJ 3614 Sunscreen(贪心)
POJ 3614 Sunscreen
题目链接
题意:转自http://blog.csdn.net/sdj222555/article/details/10698641
有C个奶牛去晒太阳 (1 <=C <= 2500),每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值,太大就晒伤了,太小奶牛没感觉。
而刚开始的阳光的强度非常大,奶牛都承受不住,然后奶牛就得涂抹防晒霜,防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。
那么为了不让奶牛烫伤,又不会没有效果。
给出了L种防晒霜。每种的数量和固定的阳光强度也给出来了
每个奶牛只能抹一瓶防晒霜,最后问能够享受晒太阳的奶牛有几个。
思路: 贪心加优先队列,牛按小值排序,防晒霜按spf值排序,然后每次一个防晒霜,就把可以的牛加入优先队列,然后每次取出牛的时候,取出右值尽量小的即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 2505; int c, l; struct SPF { int l, r; void read() { scanf("%d%d", &l, &r); } bool operator < (const SPF &c) const { return r > c.r; } } spf[N], spf2[N]; bool cmp(SPF a, SPF b) { return a.l < b.l; } int main() { while (~scanf("%d%d", &c, &l)) { for (int i = 0; i < c; i++) spf[i].read(); sort(spf, spf + c, cmp); for (int i = 0; i < l; i++) spf2[i].read(); sort(spf2, spf2 + l, cmp); int u = 0; priority_queue<SPF> Q; int ans = 0; for (int i = 0; i < l; i++) { while (u < c && spf[u].l <= spf2[i].l) Q.push(spf[u++]); while (!Q.empty() && spf2[i].r) { int tmp = Q.top().r; Q.pop(); if (tmp < spf2[i].l) continue; spf2[i].r--; ans++; } } printf("%d\n", ans); } return 0; }
POJ 3614 Sunscreen(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。