题目链接： 链接
题目大意：
有n头奶牛，它们需要晒太阳，但是接受的太阳光强度有一个区间，必须抹上防晒霜 ，然后给出 m
种防晒霜，有一个值，给牛涂上之后牛才可以晒太阳，每个防晒霜分别有kii瓶。
思路：
贪心+排序/ 平衡树实现
对于每一个头奶牛而言,当然是要选择目前来说满足条件的最差的防晒霜,什么最差的定义,就是选择满足奶牛条件的SPF最大的那一瓶防晒霜.
注意:降序排序,保证对于每一头牛而言,它用的是,可以使用的最差的防晒霜,因为值越小的防晒霜,有可能让更多的牛使用.而升序排列,就恰好反了.
就是将所有奶牛按照 minSPF 从大到小的顺序排序，然后依次考虑每头奶牛；
对于每头奶牛，扫描当前所有能用的防晒霜，选择 SPF 值最大的防晒霜来用；
平衡树的基本操作：
动态的删除某个点，动态的找到大于某个值的点 。
Code：
我要评论#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#pragma GCC optimiza(2)
#include <iostream>
#include <cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long int ll;
const int maxn = 1e4+7;
const int mod=1e9+7;
pair<int,int> cows[maxn];
map<int,int> spfs; //平衡树
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>cows[i].first>>cows[i].second;
for(int i=1;i<=m;i++){
int spf,cover;
cin>>spf>>cover;
spfs[spf]+=cover; // 要+=，因为可能会有值相同的防晒霜
}
sort(cows+1,cows+1+n); //pair自带cmp 从小到大先排序第一维然后排第二维
int ans=0;
spfs[0]=spfs[1001]=n; //平衡树两端设置哨兵
for(int i=n;i>=1;i--){ //反向枚举奶牛
auto spf=spfs.upper_bound(cows[i].second); //第一个大于这个值的spf防晒霜
spf--; //找到这个防晒霜 ，哨兵在此处的作用：防止没找到值而越界
if(spf->first>=cows[i].first) { //这个防晒霜符合条件
ans++;
if(--spf->second==0){
spfs.erase(spf);
}
}
}
cout<<ans<<endl;
return 0;
}
本文地址：https://blog.csdn.net/weixin_43872264/article/details/107522232
如对本文有疑问， 点击进行留言回复！！
网友评论