poj3614 Sunscreen

题目:

Description
To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they're at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn't tan at all........
The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle.
What is the maximum number of cows that can protect themselves while tanning given the available lotions?
Input

  • Line 1: Two space-separated integers: C and L
  • Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPFi and maxSPFi
  • Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri
    Output
    A single line with an integer that is the maximum number of cows that can be protected while tanning
    Sample Input
    3 2
    3 10
    2 5
    1 5
    6 2
    4 1
    Sample Output
    2

这道题在刚学优先队列时做过一次,当时费了许多精力,参考了大神们的文章,好不容易解决了。在很久之后的今天,又遇到了这道题,本以为会轻松解决,结果还是遇到了不小的麻烦,最后终于又一次解决了,但还是有些地方不太明白。写这篇文章来整理一下。

题意:有一群牛要晒太阳,每头牛都有spf值的下限和上限。如果阳光的spf值低于下限,则这头牛没有效果。但如果阳光的spf值高于上限,则会烧伤这头牛的皮肤。但太阳特别强烈,因此有一些不同spf值和不同数量的防晒霜。牛涂上之后阳光的spf值就变为防晒霜的spf值,只要在牛的spf的范围之内牛就能晒太阳。问最多可以让多少头牛晒太阳。

每头牛只能涂一个防晒霜,要求最大值,所以可以用贪心策略。
将防晒霜依据spf值从小到大排序,将牛按照spf下限值从小到大的顺序排序,下限值相同的按照spf上限值从小到大的顺序排序。
防晒霜从spf值小的种类开始,牛按照spf下限小的值开始。从小的值开始,就可以给大的留更多的防晒霜。我的理解是:如果给一个spf上限本来就不大的牛分了一个spf值在他范围内但很大的防晒霜,可能之后有一头spf下限很高的牛就拿不到了。
对于每一种防晒霜,只要这些牛中有下限小于等于它的就把这头牛的spf上限值进入最小堆中维护,如果不满足则轮下一种防晒霜。满足下限条件的牛只需要每次从最小堆中取出一个值(从小spf上限开始取),只要符合条件并且这种防晒霜还够就可以使用,计数器加1.如果这一种防晒霜分完了并且堆中还没空,就证明这种防晒霜已经用完了,需要轮到后面spf值大的防晒霜再判断。

参考代码:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2500+5;
const int M = 2500+5;

struct Cow {
    int mins;//最小SPF值
    int maxs;//最大SPF值
} cow[N];

struct Scr {
    int spf;//此防晒霜的SPF值 
    int cover;//此防晒霜最多可用于多少头牛
} scr[M];

int C, L;
int sz;
bool ok[N];

bool cmp(const Scr &x, const Scr &y) {
    return x.spf < y.spf;
}

bool cmp1(const Cow &x, const Cow &y) {
    if (x.mins != y.mins) return x.mins < y.mins;
    return x.maxs < y.maxs;
}

int heap[N];

void init() {
    memset(cow, 0, sizeof(cow));
    memset(scr, 0, sizeof(scr));
    memset(heap, 0, sizeof(heap));
    memset(ok, 0, sizeof(ok));
    sz = 0;
}

void push(int x) {//按照maxs的顺序从小到大

    int i = sz++;//i代表当前的下标, 然后sz加1, 代表当前数组的长度
    while (i > 0) {
        int p = (i - 1) / 2;//父亲节点的编号
        if (heap[p] <= x) break;//如果已经没有大小颠倒则退出
        //把父亲节点的数值放下来, 而把自己提上去
        heap[i] = heap[p];
        i = p;
    }

    heap[i] = x;
}

int pop() {
    //弹出maxs最小的节点
    int ret = heap[0];
    //要提到根的数值
    int x = heap[--sz];
    //从根开始向下交换
    int i = 0;
    while (i * 2 + 1 < sz) {
        //比较儿子的值
        int a = i * 2 + 1;
        int b = i * 2 + 2;
        if (b < sz && heap[b] < heap[a]) a = b;
        //如果已经没有大小颠倒则退出
        if (heap[a] >= x) break;
        //把儿子的数值提上来
        heap[i] = heap[a];
        i = a;
    }

    heap[i] = x;
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    while (cin >> C >> L) {
        init();
        int mins, maxs;
        for (int i = 0;i < C;++i) {
            cin >> cow[i].mins >> cow[i].maxs;
        }

        for (int i = 0;i < L;++i) {
            cin >> scr[i].spf >> scr[i].cover;
        }

        sort(scr, scr+L, cmp);
        sort(cow, cow+C, cmp1);

        int cnt = 0;
        
        int j = 0;
        for (int i = 0;i < L;++i) {
            while (j < C && cow[j].mins <= scr[i].spf) {
                //cout << cow[j].maxs << endl;
                push(cow[j].maxs);
                ++j;
            }

            while (sz > 0 && scr[i].cover) {
                int ret = pop();
                if (ret >= scr[i].spf) {
                    ++cnt;
                    --scr[i].cover;
                }   
            }
        }

        cout << cnt << endl;
    }
    return 0;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,884评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,347评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,435评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,509评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,611评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,837评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,987评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,730评论 0 267
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,194评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,525评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,664评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,334评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,944评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,764评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,997评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,389评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,554评论 2 349

推荐阅读更多精彩内容

  • PLEASE READ THE FOLLOWING APPLE DEVELOPER PROGRAM LICENSE...
    念念不忘的阅读 13,444评论 5 6
  • 看过美国大片的人可能会记得,经常有这样的场景,一个中枪的人,在最后一刻,听不到任何声音,只看得到所有人的嘴在动,一...
    吴国荣阅读 562评论 0 2
  • 女、儿谜西游记,一日,母携子游,子扮悟空,女扮八戒,母乐为师。 子女各显其能,百般护师,母暗喜。 悟空棒断,啼,寻...
    清尺阅读 93评论 0 0
  • Java泛型转换的事实 虚拟机中没有泛型,只要普通的类和方法 所有类型参数都用他们的限定类型替换。无限定类型的用O...
    Bejamin阅读 992评论 0 1
  • (本文作者Shawn,编辑李安迪) 作为一名和大家相同起点的成人英语学习者。这两年,我和大家一样历经挫折,走了许多...
    李安迪阅读 2,956评论 1 8