[数据结构与算法]AtCoder Beginner Contest 245 E 贪心 multiset 二分

题目

你有n个巧克力和m个盒子，巧克力和盒子都是矩形，所以每个巧克力有对应的长宽，盒子也是同理。
一个盒子只能装一个巧克力。
问所有巧克力是否都能被装下。

题解思路

贪心策略。
每个巧克力肯定是在大于等于自身长度的盒子中选择一个盒子。
选择的盒子的宽度肯定要是大于等于自身宽度的最小的一个。

不妨先满足一个条件，我们将盒子与巧克力一起按长度排序。
逆向处理，从宽度最大的往前遍历，如果是盒子加入能选择的集合中，如果是巧克力，就二分出情况来。

利用multiset就能处理二分宽度以及每个盒子选择完的删除还有重复情况。

逆向思维以及双重条件遍历满足一个都是解题的一些套路思想。

AC代码

#include <bits/stdc++.h>
//#include <unordered_map>
//priority_queue
#define PII pair<int,int>
#define ll long long

using namespace std;

const  int  INF =  0x3f3f3f3f;
const  int  N =  200100;

multiset <int> s; 
int a[N] , b[N] , c[N] , d[N] ; 
vector <array<int,3>> f ; 
void solve()
{
    int n , m ;
    cin >> n >> m ; 
    for (int i = 1 ; i <= n ; i++ )
        cin >> a[i] ; 
    for (int j = 1 ; j <= n ; j++ )
        cin >> b[j] ; 
    for (int i = 1 ; i <= m ; i++ )
        cin >> c[i] ; 
    for (int i = 1 ; i <= m ; i++ )
        cin >> d[i] ;
    for (int i = 1 ; i <= n ; i++ )
        f.push_back({a[i],b[i],0}); 
    for (int i = 1 ; i <= m ; i++ )
        f.push_back({c[i],d[i],1});
    sort(f.begin(),f.end()) ;
    reverse(f.begin(),f.end()) ; 
    for ( auto i : f )
    {
        if (i[2] == 1 )
            s.insert(i[1]) ; 
        else
        {
            auto sk = s.lower_bound(i[1]) ; 
            if ( sk == s.end() )
            {
                cout << "No\n" ; 
                return ; 
            }
            s.erase(sk) ; 
        }
    }
    cout << "Yes\n" ; 
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
        solve() ;
    return 0 ;
}