Sunscreen

Solution

先按照 minSPFminSPF 递减排序，之后找到可用的最大的防晒霜，进行安排。

证明

设 SPF[X]<SPF[Y]SPF[X]<SPF[Y] ,如果当前奶牛都可以用，那么后面的奶牛只能有三种情况

1 . X 和 Y 都可以用

2 . X 可以用， Y 不能用

3 . X ， Y 都不能用

那么可以选 Y 的影响比选 X 的小，同时带来的效益都是 1 ，所以没有区别。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,bf;
struct node{int x,y;}a[2501],c[2501];
bool cmp(node a,node b){return a.x>b.x;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
     scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1;i<=m;i++)
     scanf("%d%d",&c[i].x,&c[i].y);
    sort(a+1,a+n+1,cmp);
    sort(c+1,c+m+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
         if(c[j].x>=a[i].x&&c[j].x<=a[i].y&&c[j].y){
             c[j].y--;++bf;
             break;
         }
    }
    cout<<bf<<endl;
}