avatar
fireworks99
keep hungry keep foolish

POJ 3614 Sunscreen(贪心+优先队列)

Description

C头牛,L瓶防晒霜,

C行,每行代表每头牛既能日光浴又不会被晒伤时的spf取值范围

L行,每行代表每瓶防晒霜能使牛的spf值变成多少,以及每瓶能涂抹几头牛

求最多有几头牛可以既能晒日光浴又能不被晒伤

贪心

对牛和防晒霜从小到大排序

对于每瓶防晒霜来说,它有一个spf值,

找出所有下界小于spf的牛,放在一起

在这里面,上界也小于spf的牛可以直接扔掉(没救了)

上界大于spf即满足条件,此时防晒霜应优先给上界小的牛用

因为上界大的牛有更大的获得后续防晒霜的可能性

这里适合使用优先队列,从满足条件的牛中选出上界最小的

如果当前防晒霜用完了队列里还有牛,没关系,继续用下一瓶

Code

#include <queue> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; struct node { int l, r; }a[3000]; bool cmp(node a, node b) { if(a.l != b.l) return a.l < b.l; return a.r < b.r; } struct spf { int val, num; bool operator <(const spf & a)const { return val < a.val; } }b[3000]; int main() { int C, L; scanf("%d%d", &C, &L); for(int i = 0; i < C; ++i) scanf("%d%d", &a[i].l, &a[i].r); sort(a, a + C, cmp); for(int i = 0; i < L; ++i) scanf("%d%d", &b[i].val, &b[i].num); sort(b, b + L); int ans = 0; int idx = 0; priority_queue<int, vector<int>, greater<int> > q; for(int i = 0; i < L; ++i) { while(idx < C && b[i].val >= a[idx].l) { q.push(a[idx].r); idx++; } while(!q.empty() && b[i].num) { if(q.top() < b[i].val) { q.pop(); continue; } ans++; b[i].num--; q.pop(); } } cout << ans << '\n'; return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy