题目链接: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; }
文章评论