贪心思路
先按照每头牛的minSPF从大到小排序
然后对于每头牛选出可以用的防晒霜中(可以用的表示SPF值在范围内,并且数量大于0),SPF最大的防晒霜
为什么这样做可以呢?
我们先按每头牛的minSPF从大到小排序
那么对于当前这头牛可以使用的一些防晒霜
后面的牛的minSPF一定小于等于这些防晒霜
因为越往后minSPF越小
所以后面的牛可以使用的防晒霜就只和maxSPF(右端点)有关了
比maxSPF大的防晒霜就用不了
所以对于当前这头牛应该选择他可以使用的防晒霜中最大的一个防晒霜
因为越大的防晒霜,对于后面的牛来说就有越大的可能性是不能用的
所以当前这头牛使用它可以使用的防晒霜中SPF最大的是对后面影响最小的
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2510;
typedef pair<int , int> PII;
vector<PII> range;
vector<PII> SPF;
int n;
int l;
bool compare(PII a , PII b){
return a.first > b.first;
}
int main (){
cin >> n >> l;
for (int i = 0;i < n;i++){
int a = 0;
int b = 0;
cin >> a >> b;
range.push_back({a , b});
}
for (int i = 0;i < l;i++){
int a = 0;
int b = 0;
cin >> a >> b;
SPF.push_back({a , b});
}
sort(range.begin() , range.end() , compare);
int res = 0;
for (int i = 0;i < n;i++){
int minSPF = range[i].first;
int maxSPF = range[i].second;
int id = -1;
for (int j = 0;j < l;j++){
if(SPF[j].first >= minSPF && SPF[j].first <= maxSPF){ //能用的防晒霜
if (id == -1 && SPF[j].second > 0) {
id = j;
continue;
}
if (SPF[j].second > 0 && SPF[id].first < SPF[j].first){ //找到可以用的防晒霜中SPF最大的一个防晒霜
id = j;
}
}
}//for
if (id != -1 && SPF[id].second > 0){
SPF[id].second--; //用了一瓶防晒霜,数量减少
res++;
}
}
cout << res << endl;
return 0;
}