[ABC245]E - Wrapping Chocolate（multiset + 贪心）

题目链接：E - Wrapping Chocolate (atcoder.jp)

题目大意

有N个矩形巧克力，M个矩形盒子，一个盒子只能放最多一块巧克力，且巧克力的长和宽不能旋转，问能否装下。

思路

输入巧克力和盒子的数据，将巧克力的type设为1，盒子为0，将他们存在同一个数组里，数组大小为N + M。

将所有矩形（包括巧克力和盒子）按照宽度排降序，规则是宽更大的在左边，如果宽相同，则盒子在前，巧克力在后。

开一个序列S。

然后从左往右遍历整个数组，如果Ai是盒子就直接将长度L加入到序列S中去。

如果是巧克力，就在S中找是否存在盒子可以装下这个巧克力，所有可能的盒子都在S序列中已有的元素中，因为如果还没加进来说明宽度要比这个巧克力的宽度还要严格小。

但是如果用线性表显然不好操作，所以可以用multiset来优化复杂度，multiset的插入和删除操作的复杂度均为O(logN)，十分强大。

结合multiset自带的lower_bound方法可以二分找到所需的盒子。

我的代码在排序时使用了lambda表达式，下面这篇文章有介绍：

C++11 lambda表达式精讲 (biancheng.net)

这里还有一道使用了multiset的题目，也使用了multiset的lower_bound方法，大伙儿可以对比学习。

D - Sequence Query（二分查找，set） (eriktse.com)

代码

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int readInt()
{
	int s = 0,w = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
	while('0' <= ch && ch <= '9')s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}

const int maxn = 2e5 + 10;
int N, M;

struct rec
{
	int w, l;
	bool t;//0盒子，1巧克力 
}A[maxn * 2];

multiset<int> ss;

signed main()
{
	cin >> N >> M;
	for(int i = 1;i <= N; ++ i)
	{
		A[i].w = readInt();
		A[i].t = 1;
	}
	for(int i = 1;i <= N; ++ i)A[i].l = readInt();
	
	for(int i = N + 1;i <= N + M; ++ i)
	{
		A[i].w = readInt();
		A[i].t = 0;
	}
	for(int i = N + 1;i <= N + M; ++ i)A[i].l = readInt();
	
	sort(A + 1, A + 1 + N + M, [](rec &a,rec &b)
	{
		if(a.w != b.w)return a.w > b.w;
		return a.t == 0 && b.t == 1;
	});
	bool ans = 1;
	for(int i = 1;i <= N + M; ++ i)
	{
		int w = A[i].w, l = A[i].l;
		bool t = A[i].t;
		
		if(t == 0)ss.insert(l);
		else
		{
			auto it = ss.lower_bound(l);
			if(it == ss.end())
			{
				ans = 0;
				break;
			}
			ss.erase(it);
		}
	}
	printf("%s\n",ans ? "Yes" : "No");
	return 0;
}