1 条题解
-
0
很显然,同时对于两个条件(宽、长),我们处理得力不从心,很容易想到,先把一边条件固定下来,或处于单调性,再腾出手去处理另外一个条件。
对于本题,我们把巧克力和盒子的宽按降序排序,遍历巧克力,只要盒子的宽大于等于巧克力,就可以把盒子的高纳进来,而且可以承袭下一个巧克力,因为宽的降序,所以已经纳进来的宽一定会大于等于现在的巧克力的宽。然后需要大于等于巧克力长的最小的盒子即可。所以这里需要用到
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; }
信息
- ID
- 2729
- 时间
- 4000ms
- 内存
- 1024MiB
- 难度
- 提高
- 标签
- 递交数
- 7
- 已通过
- 1
- 上传者