很显然,同时对于两个条件(宽、长),我们处理得力不从心,很容易想到,先把一边条件固定下来,或处于单调性,再腾出手去处理另外一个条件。

对于本题,我们把巧克力和盒子的宽按降序排序,遍历巧克力,只要盒子的宽大于等于巧克力,就可以把盒子的高纳进来,而且可以承袭下一个巧克力,因为宽的降序,所以已经纳进来的宽一定会大于等于现在的巧克力的宽。然后需要大于等于巧克力长的最小的盒子即可。所以这里需要用到 multiset

(追忆似水流年:回望我那逝去的时间......)

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T = 1;
const int N = 2e5 + 10;
int n, m;

struct Size {
	int width;
	int lenth;
}chocolates[N], boxes[N];

bool Cmp(const Size& a, const Size& b) {
	if (a.width == b.width) return a.lenth < b.lenth;
	return a.width > b.width;
}

void Solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> chocolates[i].width;//a
	for (int i = 1; i <= n; i++) cin >> chocolates[i].lenth;//b
	for (int i = 1; i <= m; i++) cin >> boxes[i].width;//c
	for (int i = 1; i <= m; i++) cin >> boxes[i].lenth;//d
	sort(chocolates + 1, chocolates + 1 + n, Cmp);
	sort(boxes + 1, boxes + 1 + m, Cmp);

	// for (int i = 1; i <= n; i++) {
	// 	cout << chocolates[i].width << " " << chocolates[i].lenth << '\n';
	// }
	// cout << '\n';
	// for (int i = 1; i <= m; i++) {
	// 	cout << boxes[i].width << " " << boxes[i].lenth << '\n';
	// }

	multiset<int> ok;
	int j = 1;//boxes
	for (int i = 1; i <= n; i++) {//chocolate
		//把宽度大于等于当前的盒子都加进来
		//因为宽度降序,所以后面的宽度条件一定满足
		while (j <= m && boxes[j].width >= chocolates[i].width) {
			ok.insert(boxes[j++].lenth);
		}
		auto result = ok.lower_bound(chocolates[i].lenth);
		if (result == ok.end()) {
			cout << "No";
			return;
		}
		ok.erase(result);
	}
	cout << "Yes";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	while (T--) {
		Solve();
	}
	return 0;
}

0 条评论

目前还没有评论...