当前位置: 首页 > news >正文

建设网站公司哪家技术好达内教育

建设网站公司哪家技术好,达内教育,做电影网站的服务器需要多大,iview做的网站题目内容 原题链接 给定 n n n 个箱子&#xff0c;问是否存在一个箱子 x x x 是否可以放到另一个箱子 y y y 里。 需要满足 h x < h y , w x < w y , d x < d y h_x<h_y,w_x<w_y,d_x<d_y hx​<hy​,wx​<wy​,dx​<dy​。 箱子可以随意翻转。 …

题目内容

原题链接

给定 n n n 个箱子,问是否存在一个箱子 x x x 是否可以放到另一个箱子 y y y 里。
需要满足 h x < h y , w x < w y , d x < d y h_x<h_y,w_x<w_y,d_x<d_y hx<hy,wx<wy,dx<dy
箱子可以随意翻转。

数据范围

1 ≤ n ≤ 2 ⋅ 1 0 5 1\leq n\leq 2\cdot 10^5 1n2105
1 ≤ h i , w i , d i ≤ 1 0 9 1\leq h_i,w_i,d_i\leq 10^9 1hi,wi,di109

题解

首先按从小到大对 h , w , d h,w,d h,w,d 进行排序。

这里假设对所有的箱子,排序后都有 h ≤ w ≤ d h\leq w\leq d hwd

那么我们再按照 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_j<h_i hj<hi j j j ,且 w j < w i w_j<w_i wj<wi 的最小的 d j d_j dj 。判断 d j < d i d_j < d_i dj<di 是否成立即可。

然后在判断完后,将所有值为 h i h_i hi 的箱子都加入到树状数组中。

q u e r y ( p ) query(p) query(p) 其实是在求 w ≤ p w\leq p wp 的最小的 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;vector<Node> 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];});vector<int> 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());vector<int> 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;
}
http://www.15wanjia.com/news/18430.html

相关文章:

  • 什么是企业网站源码人民日报今天新闻
  • 廊坊高端品牌网站建设中国十大电商平台有哪些
  • 购物网站制作例子今日国际新闻头条新闻
  • 一个服务器可以备案几个网站吗白酒最有效的推广方式
  • 淘宝网站SEO怎么做google play谷歌商店
  • 上海网站设计工作室seo推广营销公司
  • 做网站的细节广告推广媒体
  • 哪家公司做网站不错营销培训课程有哪些
  • 网站做地域屏蔽seo整站优化吧
  • 关停网站的申请厦门网络推广外包多少钱
  • 做网站什么字体比较好看免费的网络推广渠道
  • wordpress多用户模版北京企业网站seo平台
  • 坡头手机网站建设快速排名刷
  • 成都市分类信息网站开发代运营竞价公司
  • 简单网站seo关键词排名价格
  • 南通做网站的公司有哪些今日国内新闻摘抄十条
  • 免费推广方法有哪些百度seo排名优化公司推荐
  • asp.net门户网站项目怎么做开电商需要多少钱
  • 临夏城乡建设局网站枸橼酸西地那非片的作用及功效
  • 班级网站制作教程定制网站开发
  • 为什么要用国外服务器做网站天天广告联盟
  • 北京网站优化seo一句话宣传自己的产品
  • 网站建设和网络推广是干嘛镇江seo
  • 哪个网站可以做卖房引擎优化seo是什么
  • 做app网站公司百度关键词排名推广话术
  • 企业网站推广网站营销引流都有什么方法
  • 北京网站开发联系电话深圳百度关键词排名
  • 好的网站推荐下 感谢企业培训内容有哪些
  • wordpress前台登陆插件哈尔滨网络推广优化
  • 注册域名需要多久seo流量是什么