《算法竞赛进阶指南》 贪心篇 防晒 （贪心+平衡树）

防晒

题目链接： 链接

题目大意：

有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