欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  网络运营

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

程序员文章站 2022-06-23 12:32:23
防晒题目链接: 链接题目大意:有n头奶牛,它们需要晒太阳,但是接受的太阳光强度有一个区间,必须抹上防晒霜 ,然后给出 m种防晒霜,有一个值,给牛涂上之后牛才可以晒太阳,每个防晒霜分别有kii瓶。思路:贪心+排序/ 平衡树实现对于每一个头奶牛而言,当然是要选择目前来说满足条件的最差的防晒霜,什么最差的定义,就是选择满足奶牛条件的SPF最大的那一瓶防晒霜.注意:降序排序,保证对于每一头牛而言,它用的是,可以使用的最差的防晒霜,因为值越小的防晒霜,有可能让更多的牛使用.而升序排列,就恰好反了....

防晒

题目链接: 链接

题目大意:

有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

相关标签: 贪心 平衡树