省住房和城乡建设厅网站,网站怎么做流量,张店网站开发招聘,wordpress ip访问题目内容 原题链接 给定 n n n 个箱子#xff0c;问是否存在一个箱子 x x x 是否可以放到另一个箱子 y y y 里。 需要满足 h x h y , w x w y , d x d y h_xh_y,w_xw_y,d_xd_y hxhy,wxwy,dxdy。 箱子可以随意翻转。
…题目内容 原题链接 给定 n n n 个箱子问是否存在一个箱子 x x x 是否可以放到另一个箱子 y y y 里。 需要满足 h x h y , w x w y , d x d y h_xh_y,w_xw_y,d_xd_y hxhy,wxwy,dxdy。 箱子可以随意翻转。
数据范围 1 ≤ n ≤ 2 ⋅ 1 0 5 1\leq n\leq 2\cdot 10^5 1≤n≤2⋅105 1 ≤ h i , w i , d i ≤ 1 0 9 1\leq h_i,w_i,d_i\leq 10^9 1≤hi,wi,di≤109
题解
首先按从小到大对 h , w , d h,w,d h,w,d 进行排序。
这里假设对所有的箱子排序后都有 h ≤ w ≤ d h\leq w\leq d h≤w≤d
那么我们再按照 h h h 为第一关键字 w w w 为第二关键字 d d d 为第三关键字对箱子进行从小到大的排序。
然后我们从按 h h h 从小到大枚举每次将所有 h h h 相同的箱子一起枚举。
这样我们就可以对剩下的 w w w 和 d d d 构建树状数组了。
对于箱子 i i i 找到 h j h i h_jh_i hjhi 的 j j j 且 w j w i w_jw_i wjwi 的最小的 d j d_j dj 。判断 d j d i d_j d_i djdi 是否成立即可。
然后在判断完后将所有值为 h i h_i hi 的箱子都加入到树状数组中。
如 q u e r y ( p ) query(p) query(p) 其实是在求 w ≤ p w\leq p w≤p 的最小的 d d d 。
这个问题又叫三维偏序。
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
代码
#include bits/stdc.h
using namespace std;const int INF 0x3f3f3f3f;struct Node {int a[3];
};int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;vectorNode vec(n);for (int i 0; i n; i) {for (int j 0; j 3; j) cin vec[i].a[j];sort(vec[i].a, vec[i].a 3);}sort(vec.begin(), vec.end(), [](const Node A, const Node B) {return A.a[0] B.a[0];});vectorint b;for (int i 0; i n; i) b.push_back(vec[i].a[1]);sort(b.begin(), b.end());b.erase(unique(b.begin(), b.end()), b.end());auto get [](int x) {return int(lower_bound(b.begin(), b.end(), x) - b.begin() 1);};for (int i 0; i n; i) vec[i].a[1] get(vec[i].a[1]);int m int(b.size());vectorint tr(m 1, INF);auto update [](int p, int x) {while (p m) {tr[p] min(tr[p], x);p (p -p);}};auto query [](int p) {int res INF;while (p 1) {res min(res, tr[p]);p - (p -p);}return res;};bool ok false;for (int i 0; i n; i) {int j i 1;while (j n vec[j].a[0] vec[i].a[0]) j 1;// 找到是否存在这么一个即可for (int k i; k j; k) {if (query(vec[k].a[1] - 1) vec[k].a[2]) {ok true;break;}}if (ok) break;// 把当前的部分全部添加进去for (int k i; k j; k) {update(vec[k].a[1], vec[k].a[2]);}i j - 1;}if (ok) cout Yes\n;else cout No\n;return 0;
}
