0x00基础算法 -- 0x06 倍增

news/2024/11/20 19:43:57/

资料来源:
算法竞赛进阶指南

活动 - AcWing

 

1、倍增

倍增:"成倍增长",指进行递推时,如果状态空间很大,通常的线性递推无法满足时间和空间复杂度的要求,就可以通过成倍增长的方式,只递推状态空间中在2的整数次幂位置上的值作为代表。当需要其他位置上的值时,通过"任意整数可以表示成若干个2的次幂项的和"这一性质,使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求递推的问题的状态空间关于2的次幂具有可划分性。

倍增思想二进制划分思想相互结合,可以降低求解很多问题的时间和空间复杂度。例如:“快速幂”

//求 m^ k mod p,时间复杂度 O(logk)。int qmi(int m, int k, int p)
{int result = 1;int t = m;while (k){if (k & 1)result = result * t % p;t = t * t % p;k >>= 1;}return result;
}

1.1 问题一

给定一个长度为N的数列A,进行若干次询问,每次给定一个整数T,求出最大的k,满足\sum_{i=1}^{k}A[i]\leq T,你的算法必须时在线的(必须即时回答每一个询问,不能等待收到所有询问后再统一处理),假设0\leq T\leq \sum_{i=1}^{k}A[i]

朴素做法:
从前向后枚举k位,最坏情况位O(N) 。

前缀和+二分:
O(N)处理前缀和,每次询问通过二分比较S[k]与T的大小来确定二分上下界的变化,每次询问花费的时间都是O(log N)。
平均情况下该算法很好,但缺点就是如果每次询问给定的整数T都非常小,造成答案k也非常小,那么该算法可能还不如从前向后枚举更优。 

前缀和+倍增算法

  1. 令p=1,k=0,sum=0
  2. 比较“A数组中k之后的p个数的和”与T的关系,也就是说,如果sum+S[k+p]-S[k]<=T,则令sum+=S[k+p]-S[k],k+=p,p*=2,即累加上这p个数的和,然后把p的跨度增长一倍。如果sum+S[k+p]-S[k]>T,则令 p/=2
  3. 重复上一步,直到p的值变为0,此时k就是答案

通过若干个长度为2次幂的区间拼成最后的k,时间复杂度级别为答案的对数,能够应对T的各种大小情况。
 

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL; const int N = 1e6 + 10;
LL S[N];//前缀和
int n,m;//n为数组个数,m表示询问次数int main()
{cin >> n >> m;for(int i = 1; i <= n; i++){int a;cin >> a;S[i] = S[i - 1] + a;}while(m--){int t;cin >> t;int p = 1, k = 0, sum = 0; //A数组中k之后的p个数的和while(p) //p为0结束{//注意越界问题if(k + p <= n && sum + S[k+p] - S[k] <= t)sum += S[k+p] - S[k], k = k + p <= n ? k + p : n, p *= 2;else //sum + S[k+p] - S[k] > tp /= 2;}cout << k << endl;}return 0;
}

1.2 题目 -- 天才ACM

109. 天才ACM - AcWing题库 


思路:

  1. 对于一个集合S,显然应该取S中最大的M个数和最小的M个数,最大和最小的构成一对,次大和次小构成一对...这样求得的"校验值"最大。
  2. 求校验值需要进行排序,选取其中最大和最小分别M个值进行计算。
  3. 为了让数列A分成的段数最少,每一段都应该在"校验值"不超过T的情况下,尽量包含更多的数,所以从头开始对A进行分段,让每一段尽量长,到达结尾时分成的段数就是答案。
  4. 转化问题为:当确定一个左端点L之后,右端点R在满足A[L]~A[R]的"校验值'不超过T的前提下,最大能取到多少。
  5. 求某一段的"校验值"需要排序配对,时间复杂度为O(N log N)
  6. 利用倍增算法
    令p=1,R=L
    求出[L,R+p]区间的"校验值",若"校验值"<=T,则R += p,p *= 2;否则,p /= 2
    重复上一步,直到p的值为0,此时R即为所求。
    上述过程至多循环O(log N)次,每次循环需要排序,完成整个题目的求解累计扩展长度为N,所以总体时间复杂度为O(N log^{2}N)。可以通过归并排序,只对新增的长度部分排序,然后合并新旧两端,这样总体时间复杂度降低到O(N log N)。
#include <iostream>
#include <algorithm>using namespace std;typedef long long ll;const int N = 500005;int n, m;
int ans;
ll T;
ll w[N], t[N];
ll tmp[N];ll sq(ll x)
{return x * x;
}bool check(int l, int mid, int r)           // 判断区间 [l, r) 是否合法,并将 t 中的 [l, mid) 区间和 [mid, r) 区间合并到 tmp 中
{for (int i = mid; i < r; i ++ )         // 将 w 数组的 [l, r) 区间复制到 t 的 [l, r) 区间中t[i] = w[i];sort(t + mid, t + r);                   // 将 t 的 [mid, r) 排序int i = l, j = mid, k = 0;              // 双指针进行区间合并while (i != mid && j != r)              // 当 i 不到 mid 且 j 不到 r 时,执行循环if (t[i] < t[j])                    // 如果 t[i] 比 t[j] 小,那么将 t[i] 放入 tmp 中tmp[k ++ ] = t[i ++ ]; else                                // 否则将 t[j] 放入 tmp 中tmp[k ++ ] = t[j ++ ];while (i != mid) tmp[k ++ ] = t[i ++ ]; // 处理剩下的元素while (j != r) tmp[k ++ ] = t[j ++ ];ll sum = 0;                             // 计算校验值for (i = 0; i < m && i < k; i ++ , k -- )sum += sq(tmp[i] - tmp[k - 1]);return sum <= T;                        // 返回当前区间 [l, r) 是否合法
}int main()
{int K;scanf("%d", &K);while (K -- ){scanf("%d %d %lld\n", &n, &m, &T);for (int i = 0; i < n; i ++ )scanf("%lld", &w[i]);ans = 0;int len;int start = 0, end = 0;while (end < n){len = 1;while (len){if (end + len <= n && check(start, end, end + len)) // 如果 w 的 [start, end + len) 区间合法{end += len, len <<= 1;if (end >= n) break ;               // 一个小剪枝,如果 end >= n,那么直接跳出for (int i = start; i < end; i ++ ) // 在 check 时,已经将 t 数组的 [start, end + len) 这段区间归并在 tmp 中了。现在只需要将 tmp 中的有序数组复制到 t 中即可t[i] = tmp[i - start];          // 复制的时候注意下标变换,tmp 是从 0 开始存的,t 是从 start 开始存的}else    len >>= 1;}start = end;ans ++ ;}printf("%d\n", ans);}return 0;
}

2、ST算法

在区间最值问题(RMQ)中,ST算法就是倍增的产物。给定一个长度为N的数列A,ST算法能在O(N log N)时间的预处理后,以O(1)的时间复杂度在线回答"数列A中下标在"l~r"之间的数的最值是多少"。 

设F[i,j]表示数列A中下标在子区间[i,i + 2^j - 1]里的数的最大值,也就是从i开始的2^j个数的最大值。递推边界显然是F[i,0] = A[i],即数列A在子区间[i,i]里的最大值。 

在递推时,把子区间的长度成倍增长,有公式:f[i,j] = max(f[i,j-1],F[i+2^{j-1},j-1]),即长度为2^j的子区间的最大值是左右两半长度为2^(j-1)的子区间的最大值中较大的一个。

void ST_prework()
{for(int i = 1; i <= n; i++)f[i][0] = a[i];int t = log(n) / log(2) + 1; //利用对数换底公式,将底数e换成2;for(int j = 1; j < t; j++)for(int i = 1; i <= n - (1 << j) + 1; i++)f[i][j] = max(f[i][j-1],f[i + (1<<(j-1))][j-1]);
}

当询问任意区间[l,r]的最值时,需要先计算一个k,满足2^{k}< r-l+1\leq 2^{k+1},使2的k次方小于区间长度的前提下最大的k,那么“从l开始的2^k个数”和“以r结尾的2^k个数”这两段覆盖了整个[l,r],这两段的最大值分别是F[l,k]和F[r-2^k+1,k],二者中较大的那个就是整个区间[l,r]的最值。

int ST_query(int l, int r)
{int k = log(r - l + 1) / log(2); //对数换底:log 2 (r - l + 1)return max(f[l][k],f[r - (1 << k) + 1][k]);
}

 


http://www.ppmy.cn/news/1548553.html

相关文章

如何使用虚拟机 打开另一个虚拟机的 硬盘

问题&#xff1a; 我在鼓捣一个虚拟机的 nvim 的时候&#xff0c;突然搞成 segment fault , 系统无法启动&#xff0c;但是&#xff0c;我编译的源码还在 这个虚拟机中。 解决过程&#xff1a; 直接使用 另一个 虚拟机&#xff0c; 添加这个虚拟机的硬盘。 我之前的虚拟机是这…

Python设计模式详解之5 —— 原型模式

Prototype 设计模式是一种创建型设计模式&#xff0c;它通过复制已有的实例来创建新对象&#xff0c;而不是通过从头实例化。这种模式非常适合对象的创建成本较高或者需要避免复杂的构造过程时使用。Prototype 模式提供了一种通过克隆来快速创建对象的方式。 1. Prototype 模式…

Mac 修改默认jdk版本

当前会话生效 这里演示将 Java 17 版本降低到 Java 8 查看已安装的 Java 版本&#xff1a; 在终端&#xff08;Terminal&#xff09;中运行以下命令&#xff0c;查看已安装的 Java 版本列表 /usr/libexec/java_home -V设置默认 Java 版本&#xff1a; 找到 Java 8 的安装路…

鸿蒙NEXT开发案例:计数器

【引言】&#xff08;完整代码在最后面&#xff09; 本文将通过一个简单的计数器应用案例&#xff0c;介绍如何利用鸿蒙NEXT的特性开发高效、美观的应用程序。我们将涵盖计数器的基本功能实现、用户界面设计、数据持久化及动画效果的添加。 【环境准备】 电脑系统&#xff1…

STM32单片机CAN总线汽车线路通断检测-分享

目录 目录 前言 一、本设计主要实现哪些很“开门”功能&#xff1f; 二、电路设计原理图 1.电路图采用Altium Designer进行设计&#xff1a; 2.实物展示图片 三、程序源代码设计 四、获取资料内容 前言 随着汽车电子技术的不断发展&#xff0c;车辆通信接口在汽车电子控…

openeuler设置IP

1 编辑网络配置文件&#xff1a;通常在/etc/sysconfig/network-scripts/目录下&#xff0c;对应的网络接口配置文件名为ifcfg-&#xff0c;例如ifcfg-eth0。 2. 修改配置文件&#xff1a;将BOOTPROTO的值改为static&#xff0c;并设置IPADDR、NETMASK、GATEWAY和DNS等参数。…

Clip结合Faiss+Flask简易版文搜图服务

一、实现 使用目录结构&#xff1a; templates ---upload.html faiss_app.py 前端代码&#xff1a;upload.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content&quo…

【企业级分布式系统】ELK优化

文章目录 Elasticsearch作为日志存储时的优化优化ES索引设置优化线程池配置锁定内存&#xff0c;不让JVM使用Swap减少分片数、副本数 Elasticsearch作为日志存储时的优化 linux内核优化、JVM优化、ES配置优化、架构优化&#xff08;filebeat/fluentd代替logstash、加入kafka做…