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

分治算法

本文代码适用于c++

引入

现在来了一队女生共n人,但是我们得知其中有一位是小南娘。我们如何快速找到那位小南娘呢?

每次查询一个队列我们可以得到该队列中是否存在南娘。

不难想到,我们可以将这n人均分成两组,然后再将含有小南娘的那一组继续均分......直到最小的组只有一人。这样时间复杂度为O(log n)。

在解决上面查小南娘的问题中我们正是使用了分治的思想。分治算法的要点在于【拆】:如何将问题拆分为小问题;【合】:将小问题的解合并为最终问题的解。

下面我们看几个典型的例子。

归并排序

给定一个数列a,将它排序。

分析

考虑如何【拆】【合】

  1. 【拆】:不难想到,只需将数列分成几个小数列分别排序即可。当数列只有一元时它就天然有序。
  2. 【合】:如何将两个有序的数列合并成一个有序的数列呢?我们可以用双指针轻松解决

双指针即定义两个指针i,j。
对于两个有序数列a,b:
(不妨两者都是从小到大)
初始令i=j=1(i,j分别用来访问a,b)
每次操作将ai,bj中较小的一项加入数列c,并且让最小一项对应的指针加一。
这样经过|a|+|b|次操作,我们就可以将两个有序数列合并为新的有序数列

代码实现

#include <iostream>
#include <cstdio>
using namespace std;long long n, cnt = 0;
long long a[500005];
long long tmp[500005];void merge(int l, int mid, int r)
{int i = l, j = mid + 1, k = l;while (i <= mid && j <= r){if (a[i] <= a[j]){tmp[k++] = a[i++];}else{tmp[k++] = a[j++];}}while (i <= mid) tmp[k++] = a[i++];while (j <= r) tmp[k++] = a[j++];for (int m = l; m <= r; m++) a[m] = tmp[m];
}void doit(int l, int r)
{if (l >= r) return; // 递归终止条件(单个元素无需排序)int mid = (l + r) / 2;doit(l, mid);       // 排序左子数组(l~mid)doit(mid + 1, r);   // 排序右子数组(mid+1~r)merge(l, mid, r);   // 合并两个有序子数组
}int main()
{cin >> n;for (int i = 1; i <= n; i++){scanf("%lld", &a[i]);}doit(1, n);for (int i = 1; i <= n; i++) {cout << a[i] << " ";}return 0;
}

逆序对

问题

给定数列a,求满足i>j,ai<aj的(i,j)个数。

分析

  1. 【拆】 [l,r]拆分为[l,mid]和[mid+1,r]。当区间长度为1时没有逆序对。
  2. 【合】 [l,r]中的逆序对无非三种:
    (1) i,j都在[l,mid]中
    (2) i, j都在[mid+1,r]中
    (3) i,j分别在两个区间中

问题在于如何求解(3)类中的逆序对个数。

由于每个子区间中的逆序对个数已经确定,其内部的序已经不重要,我们可以将子区间内部进行排序,然后通过双指针的方法解决。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;long long n, cnt = 0;
long long a[500005];
long long tmp[500005];void merge(int l, int mid, int r)
{int i = l, j = mid + 1, k = l;while (i <= mid && j <= r){if (a[i] <= a[j]){tmp[k++] = a[i++];}else{// 左子数组剩余元素都与a[j]构成逆序对cnt += mid - i + 1;tmp[k++] = a[j++];}}while (i <= mid) tmp[k++] = a[i++];while (j <= r) tmp[k++] = a[j++];for (int m = l; m <= r; m++) a[m] = tmp[m];
}void doit(int l, int r)
{if (l >= r) return; // 递归终止条件(单个元素无需排序)int mid = (l + r) / 2;doit(l, mid);       // 排序左子数组(l~mid)doit(mid + 1, r);   // 排序右子数组(mid+1~r)merge(l, mid, r);   // 合并两个有序子数组
}int main()
{cin >> n;for (int i = 1; i <= n; i++){scanf("%lld", &a[i]);}doit(1, n);cout << cnt << endl; // 可选:输出逆序对数量
//	for (int i = 1; i <= n; i++) {
//		cout << a[i] << " ";
//	}return 0;
}
http://www.hskmm.com/?act=detail&tid=33835

相关文章:

  • 专用硬件神经网络优化技术解析
  • 学习逆向的背景知识(自用)
  • Linux-网络安全私房菜(二)
  • pycharm使用远程的ssh的解释器
  • Android SSL Pinning检测利器:SSLPinDetect技术解析
  • AI元人文:社区调解的数字剧场
  • 2025年粉末冶金制品/零件厂家推荐排行榜,专业制造与高品质服务的首选!
  • Dubbo入门-Dubbo的快速使用
  • 站位2
  • 傅里叶变换及DCT点滴
  • 【未完待续】MkDocs 部署安装教程
  • 傅里叶变换点滴
  • [PaperReading] SAIL-Embedding Technical Report: Omni-modal Embedding Foundation Model
  • 人生四大支柱 - 健康,金钱,工作,关系
  • 英伟达个人AI超算Spark技术解析
  • [buuctf]jarvisoj_level3_x64
  • SpringBoot系列十三:SpringBoot面试常见问题
  • [LangChain] 04. 提示词模板
  • 2025 最新不锈钢板厂家推荐榜:剖析国内头部品牌竞争优势,附优质供应商选择指南N06625/N06600/C70600不锈钢板厂家推荐
  • 2025 夹丝玻璃源头厂家最新推荐排行榜:解析防火 / 艺术 / 酒店等多场景厂商优势,助力精准选型
  • 2025 中空板源头厂家最新推荐排行榜揭晓:覆盖全产业链,老牌与新锐共筑品质标杆
  • 2025 年感温电缆厂家最新推荐榜单:覆盖线型 / 缆式 / 可恢复 / 消防等多类型产品,全方位解析头部企业核心优势
  • 2025 年盖板源头厂家最新推荐榜单:电力 / 隧道 / 电缆沟等多场景适用品牌优选,解析原材料采购与成本控制要点
  • win
  • 2025 年真空炉制造厂家最新推荐排行榜:涵盖高温烧结真空炉 / 真空退火炉 / 智能铍铜真空炉,助力企业精准选型
  • 2025 年最新推荐排水沟厂家排行榜:聚焦树脂 / 线性 / 树脂混凝土 / 成品 / U 型排水沟优质企业
  • 将 XMind 测试用例转换为 CSV 文件导入测试管理平台
  • 互评-OO之接口-DAO模式代码阅读及应用
  • experiment2
  • 【为美好CTF献上祝福】unity逆向