【POJ 3614 Sunscreen】贪心 优先级队列

题目链接:http://poj.org/problem?id=3614

题意:C头牛去晒太阳,每头牛有自己所限定的spf安全范围[min, max];有L瓶防晒液,每瓶有自己的spf值和容量(能供几头牛用)。

求这L瓶防晒液最多能让多少头牛安全地晒太阳。

思路:贪心策略,按spf从小到大或从大到小的顺序取出防晒液,供给尽可能多的剩余的牛。

具体如何判断当前这瓶防晒液最多能供给几头牛呢?

以spf从小到大排序所有防晒液为例,可以维护一个小顶堆,每取出一瓶防晒液l,就把剩余的所有min值低于l.spf的牛的max值放入堆中。

接下来在l的容量尚未耗尽时,反复弹出并比较堆顶值与l.spf,若大于l.spf,则 l 消耗1单位的容量供给这头牛,计数值加1;否则这头牛不能被任何防晒液供给(当前spf已经是剩余的最小值,后续不会有更小的)。反复取堆顶元素直至容量耗尽或堆变空。各瓶防晒液的计数值的总和即为答案。

首先需要将防晒液按spf值从小大到排序(O(LlogL)),以及将牛按min值从小到大排序(O(ClogC));然后外层循环对L瓶防晒液进行一遍扫描(O(L)),内层循环每头牛的max必然入堆一次、弹出一次(Ω(C)),所以总的复杂度为O(LlogL + CLogC + LC)。

自己实现的堆,时间上总是比STL的priority_queue慢一些,不过空间更少。

  1 #include <cstdio>
  2 #include <algorithm>
  3 using namespace std;
  4 const int MAX_C = 2505;
  5 const int MAX_L = 2505;
  6 int C, L;
  7 struct Cow
  8 {
  9     int min, max;
 10     Cow& operator = (Cow& c){
 11         min = c.min;
 12         max = c.max;
 13         return *this;
 14     }
 15 }cows[MAX_C];
 16
 17 struct Lotion
 18 {
 19     int spf,cover;
 20 }lotions[MAX_C];
 21
 22 bool cmpL(Lotion l1, Lotion l2){
 23     return l1.spf < l2.spf;
 24 }
 25 bool cmpC(Cow c1, Cow c2){
 26     return c1.min < c2.min;
 27 }
 28
 29 int heap[MAX_C]; //小顶堆
 30 int size = 0;
 31
 32 void swap(int& x, int& y){
 33     int tmp = x;
 34     x = y;
 35     y = tmp;
 36 }
 37
 38 void insert(int x){
 39     size++;
 40     heap[size-1] = x;//目标元素暂时插到末尾
 41     int i = size - 1;//候选目标位置
 42     while(i > 0){     //上滤,反复与父节点比较
 43         int p = (i-1)/2;
 44         if(heap[p] > heap[i]){//与父节点违反堆序性时
 45             swap(heap[i], heap[p]);//父节点下沉
 46             i = p; //候选位置攀升
 47         }else break;
 48     }
 49 }
 50
 51 void deleteTop(){
 52     heap[0] = heap[size-1];
 53     size--;
 54     int i = 0; //候选目标位置
 55     while(i*2+1 < size){//下滤
 56         int lc = i*2+1;
 57         int rc = i*2+2;
 58         int c = lc;
 59         if(rc<size && heap[rc]<heap[lc])
 60             c = rc;
 61         if(heap[c] < heap[i]){
 62             swap(heap[c], heap[i]);//孩子节点攀升
 63             i = c;//候选位置下沉
 64         }else break;
 65     }
 66 }
 67
 68 int getTop(){
 69     return heap[0];
 70 }
 71
 72 int main()
 73 {
 74     freopen("3614.txt", "r", stdin);
 75     scanf("%d%d", &C, &L);
 76     for(int i=0; i<C; i++){
 77         scanf("%d%d", &cows[i].min, &cows[i].max);
 78     }
 79
 80     for(int i=0; i<L; i++){
 81         scanf("%d%d", &lotions[i].spf, &lotions[i].cover);
 82     }
 83
 84     sort(lotions, lotions+L, cmpL);
 85     sort(cows, cows+C, cmpC);
 86
 87     int cnt = 0;
 88     for(int i=0, j=0; i<L; i++){
 89         //printf("lotion %d %d\n", lotions[i].spf, lotions[i].cover);
 90         while(j<C && cows[j].min <= lotions[i].spf){
 91             insert(cows[j].max);
 92             j++;
 93             //printf("insert %d\n", cows[j-1].max);
 94         }
 95         int vol = lotions[i].cover;
 96
 97         while(vol > 0 && size>0){
 98             if(getTop() >= lotions[i].spf){
 99                 vol--;
100                 cnt++;
101                 //printf("add %d\n", getTop());
102             }
103             deleteTop();
104             //printf("%d\n", cnt);
105         }
106     }
107     printf("%d\n", cnt);
108     return 0;
109 }

 

时间: 2024-10-04 12:32:56

【POJ 3614 Sunscreen】贪心 优先级队列的相关文章

C++:库函数优先级队列(priority_queue)输出最小值 代码

库函数优先级队列(priority_queue)的实现方式是堆(heap), 默认是输出最大值. 输出最小值, 需要指定参数, priority_queue<int, vector<int>, greater<int> > 代码: /* * main.cpp * * Created on: 2014.7.20 *更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/cplus/ * Author:

浅谈算法和数据结构 五 优先级队列与堆排序

在很多应用中,我们通常需要按照优先级情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次高的对象.最简单的一个例子就是,在手机上玩游戏的时候,如果有来电,那么系统应该优先处理打进来的电话. 在这种情况下,我们的数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象.这种数据结构就是优先级队列(Priority Queue) . 本文首先介绍优先级队列的定义,有序和无序数组以及堆数据结构实现优先级队列,最后介绍了基于优先级队列的堆排序(Heap Sort) 更

Java数组模拟优先级队列数据结构的实例_java

优先级队列如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了.这样,我们就引入了优先级队列 这种数据结构. 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素 (3)删除 一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 .对于优先权相同的元素,可按先进先出次序处理或按任意优先权

优先级队列实现哈夫曼树的编码和译码

//优先级队列实现的哈夫曼树的编码和译码 #include<iostream> #include<queue> #include<string> using namespace std; class Node { public: float weight; Node* left; Node* right; char ch; Node(float w,Node* l=NULL,Node* r=NULL,char c=' '):weight(w),ch(c),left(l)

stl的优先级队列

#include <iostream> #include <vector> #include <queue> using namespace std; class Timer; typedef Timer* RTimer; class Timer { public: Timer():_interval(0),_expires_time(0){} virtual ~Timer(){} virtual void schedule_timer(int sec,int usec

[算法系列之四]优先级队列

[概念] 优先级队列,顾名思义,就是一种根据一定优先级存储和取出数据的队列.它可以说是队列和排序的完美结合体,不仅可以存储数据,还可以将这些数据按照我们设定的规则进行排序.优先级队列是堆的一种常见应用.有最大优先级队列(最大堆)和最小优先级队列(最小堆).优先级队列是一种维护有一组元素构成的集合S的数据结构. [优先队列支持的基本运算] [cpp] view plaincopy //建立一个保存元素为int的优先级队列,其实是建了一个小顶堆   //但是请特别注意这样的建的堆默认是大顶堆,即我们

link中如何用大根堆小根堆实现优先级队列?是不是需要自己写数据结构?

问题描述 link中如何用大根堆小根堆实现优先级队列?是不是需要自己写数据结构? link中如何用大根堆小根堆实现优先级队列?是不是需要自己写数据结构? 解决方案 参考:http://download.csdn.net/download/Miu__Y/3309472

云计算设计模式(十六)——优先级队列模式

云计算设计模式(十六)--优先级队列模式 优先发送到服务,以便具有较高优先级的请求被接收和高于一个较低优先级的更快速地处理请求.这种模式是在应用程序是有用的,它提供不同的服务级别保证或者针对独立客户. 背景和问题 应用程序可以委托给其他服务的具体任务;例如,为了执行后台处理或与其他应用程序或服务的整合.在云中,消息队列通常用于将任务委派给后台处理.在许多情况下,请求由服务接收的顺序是不重要的.然而,在某些情况下,可能需要优先考虑的具体要求.这些要求必须早于较低优先级的其他可能先前已发送由应用程序

link环境下如何实现有序优先级队列?大根堆小根堆能用的么?

问题描述 link环境下如何实现有序优先级队列?大根堆小根堆能用的么? link环境下如何实现有序优先级队列?大根堆小根堆能用的么? 解决方案 自己用Queue构建一个就可以了.