奶牛晒太阳


题目描述

有 C 头奶牛去晒太阳,每头奶牛各自能够忍受的阳光强度有一个最小值和一个最大值,太大就晒伤了,太小奶牛没感觉。而刚开始的阳光的强度非常大,奶牛都承受不住,奶牛得涂抹防晒霜,防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。那么为了不让奶牛烫伤,又不会没有效果。给出了 L 种防晒霜固定的阳光强度和数量,每头奶牛只能抹一瓶防晒霜,求能够享受晒太阳的奶牛最多有几头。


输入

第一行输入两个数 C,L。(1≤C,L≤2500)

接下来 C 行,每行两个数表示每头奶牛能接受的阳光强度的最小值和最大值。(均小于 1000)

再接下来 L 行,每行两个数表示每种防晒霜固定的阳光强度和数量。(均小于 1000)

输出

输出能晒太阳的奶牛的最多数量。


样例输入

3 2
3 10
2 5
1 5
6 2
4 1

样例输出

2

数据规模与约定

时间限制:1 s

内存限制:256 M

100% 的数据保证 1≤C,L≤2500

题意

把问题描述为,对于每个区间,尽可能让更多的点落在区间上,每个区间只能落一个点;
奶牛比作区间,防晒霜比作点。

贪心策略

对于区间a, b;

  • 1、若a包含b,则先处理b(小区间) ———–顺序相关
  • 2、若a, b区间有交集,则先处理左边界l小的那个 ——— 策略相关
  • 3、没有交集,先处理哪个都一样

题解

#include <stdio.h>
#include <algorithm>
using namespace std;
/*

贪心策略:
对于区间a, b;
1、若a包含b,则先处理b(小区间) -----------顺序相关 
2、若a, b区间有交集,则先处理左边界l小的那个    --------- 策略相关 
3、没有交集,先处理哪个都一样 
*/
 
struct Node {
    int l, r; //l表示左边界,r表示右边界 
    bool operator< (const Node &a) const {
        //重载小于号,使其排序的时候满足我们的贪心策略的顺序相关 
        if (this->l ^ a.l) return this->l > a.l; //左边界不相等时,左边界大的也就是小区间在前面 
        return this->r < a.r;//左边界相等时,右边界小的也就是小区间在前面 
    }
};

Node num[2505]; // 奶牛 ( 区间 ) 
int fs[1000]; //每种防晒值的防晒的防晒霜 ( 点 ) 的数量
int main() {
    int c, l, ans = 0;
    scanf("%d %d", &c, &l);
    for (int i = 1; i <= c; i++) scanf("%d %d", &num[i].l, &num[i].r);
    sort(num + 1, num + 1 + c); //处理顺序相关
    for (int i = 1, a, b; i <= l; i++) {
        scanf("%d %d", &a, &b);
        fs[a] += b;
    }
    for (int i = 1; i <= c; i++) {
        //根据顺序相关排序后,处理我们的策略相关 
        for (int j = num[i].r; j >= num[i].l; j--) {
            if (fs[j] == 0) continue;
            --fs[j];
            ++ans;
            break;
        }
    }
    printf("%d\n", ans);
    return 0;
}

文章作者: Axieyun
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Axieyun !
评论
评论
  目录