1 条题解

  • 0
    @ 2026-9-1 21:35:49

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

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

    信息

    ID
    2729
    时间
    4000ms
    内存
    1024MiB
    难度
    提高
    标签
    递交数
    7
    已通过
    1
    上传者