题目描述

有C头奶牛进行日光浴，第i头奶牛需要minSPF[i]到maxSPF[i]单位强度之间的阳光。

每头奶牛在日光浴前必须涂防晒霜，防晒霜有L种，涂上第i种之后，身体接收到的阳光强度就会稳定为SPF[i]，第i种防晒霜有cover[i]瓶。

求最多可以满足多少头奶牛进行日光浴。

输入格式
第一行输入整数C和L。

接下来的C行，按次序每行输入一头牛的minSPF和maxSPF值,即第i行输入minSPF[i]和maxSPF[i]。

再接下来的L行，按次序每行输入一种防晒霜的SPF和cover值,即第i行输入SPF[i]和cover[i]。

每行的数据之间用空格隔开。

样例

输出格式
输出一个整数，代表最多可以满足奶牛日光浴的奶牛数目。

数据范围
1≤C,L≤2500,
1≤minSPF≤maxSPF≤1000,
1≤SPF≤1000
输入样例：
3 2
3 10
2 5
1 5
6 2
4 1
输出样例：
2

算法1

(贪心) $O(nm)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2510;

int n,m;

struct Cow{
    int l,r;

    bool operator<(const Cow& p){
        //if(l == p.l)return r < p.r;
        return r < p.r;
    }

}cow[N];

struct W{
    int v,cnt;
    bool operator<(const W& p)
    {
        return v < p.v;
    }
}a[N];

bool st[N];
int main(){

   cin >> n >> m;

   for(int i = 1 ; i <= n ;i++)cin >> cow[i].l >> cow[i].r;
     sort(cow + 1 , cow + n + 1);
   for(int i = 1 ; i <= m;i++)cin >> a[i].v >> a[i].cnt;


    sort(a + 1 , a + m + 1);
    int ans = 0;

    for(int i = 1 ; i <= n ;i++)
      {
          for(int j = 1 ; j <= m ;j++)
            if(a[j].cnt > 0 && a[j].v<=cow[i].r && a[j].v >= cow[i].l)
            {
                ans++;
                a[j].cnt--;
                break;
            }

      }
      //if(ans == 26)cout << 27 << endl;
      cout << ans << endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla