- 题解
- ABC245E 包装巧克力
ABC245E. 包装巧克力
- @ 2026-9-1 21:36:36
很显然,同时对于两个条件(宽、长),我们处理得力不从心,很容易想到,先把一边条件固定下来,或处于单调性,再腾出手去处理另外一个条件。
对于本题,我们把巧克力和盒子的宽按降序排序,遍历巧克力,只要盒子的宽大于等于巧克力,就可以把盒子的高纳进来,而且可以承袭下一个巧克力,因为宽的降序,所以已经纳进来的宽一定会大于等于现在的巧克力的宽。然后需要大于等于巧克力长的最小的盒子即可。所以这里需要用到 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 条评论
目前还没有评论...