[第二章]二分与前缀和

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: [第二章]二分与前缀和


题目一解析

给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。

对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。

如果数组中不存在该元素,则返回“-1 -1”。

输入格式

第一行包含整数n和q,表示数组长度和询问个数。

第二行包含n个整数(均在1~10000范围内),表示完整数组。

接下来q行,每行包含一个整数k,表示一个询问元素。

输出格式

共q行,每行包含两个整数,表示所求元素的起始位置和终止位置。

如果数组中不存在该元素,则返回“-1 -1”。

数据范围

1≤n≤100000

1≤n≤100000

1≤q≤10000

1≤q≤10000

1≤k≤10000

1≤k≤10000

样例

输入样例:

6 3

1 2 2 3 3 4

3

4

5

输出样例:

3 4

5 5

-1 -1

算法原理

本题是练习二分很好的一道题目,二分程序虽然简单,但是如果写之前不考虑好想要查找的是什么,十有八九会是死循环或者查找错误,就算侥幸写对了也只是运气好而已。

用二分去查找元素要求数组的有序性或者拥有类似于有序的性质,对本题而言,一个包含重复元素的有序序列,要求输出某元素出现的起始位置和终止位置,翻译一下就是:在数组中查找某元素,找不到就输出−1

找到了就输出不小于该元素的最小位置和不大于该元素的最大位置。所以,需要写两个二分,一个需要找到>=x的第一个数,另一个需要找到<=x的最后一个数。查找不小于x的第一个位置,较为简单:

int l = 0, r = n - 1;
while (l < r) {
    int mid = l + r >> 1;
    if (a[mid] < x)  l = mid + 1;
    else    r = mid;
}

当a[mid]<x时,令l=mid+1,mid及其左边的位置被排除了,可能出现解的位置是mid+1及其后面的位置。

当a[mid]>=x时,说明mid及其左边可能含有值为x的元素。

当查找结束时,l与r相遇,l所在元素若是x则一定是x出现最小位置,因为l左边的元素必然都小于x。

查找不大于x的最后一个位置,便不容易了:

int l1 = l, r1 = n;
while (l1 + 1 < r1) {
    int mid = l1 + r1 >> 1;
    if (a[mid] <= x)  l1 = mid;
    else    r1 = mid;
}

要查找不大于x的最后一个位置:

当a[mid]<=x时,待查找元素只可能在mid及其后面,所以l=mid;

当a[mid]>x时,待查找元素只会在mid左边,令r=mid。

int l = 0, r = n - 1;
while (l < r)
 {
        int mid = l + r + 1 >> 1;
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
 }

int l1 = l, r1 = n - 1;
while (l1 < r1) {
    int mid = l1 + r1 >> 1;
    if (a[mid] <= x)  l1 = mid + 1;
    else    r1 = mid - 1;
}
printf("%d %d\n", l, l1 - (a[l1] == x ? 0 : 1));

代码实现

#include <iostream>
using namespace std;
const int maxn = 100005;
int n, q, x, a[maxn];
int main() 
{
    cin>>n>>q;
    for (int i = 0; i < n; i++)
        cin>>a[i];
    while (q--) 
    {
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r) 
        {
            int mid = l + r >> 1;
            if (a[mid] < x)  l = mid + 1;
            else    r = mid;
        }
        if (a[l] != x)
        {
            printf("-1 -1\n");
            continue;
        }
        int l1 = l, r1 = n;
        while (l1 + 1 < r1) 
        {
            int mid = l1 + r1 >> 1;
            if (a[mid] <= x)  l1 = mid;
            else    r1 = mid;
        }
        cout<<l<<" "<<l1<<endl;
    }
    return 0;
}

题目二解析

给定一个浮点数 n,求它的三次方根。

输入格式

共一行,包含一个浮点数 n。

输出格式

共一行,包含一个浮点数,表示问题的解。

注意,结果保留 6 位小数。

数据范围

−10000≤n≤10000

输入样例:

1000.00

输出样例:

10.000000

算法原理

这道题是一个浮点二分的题目

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
double x;
int main() 
{
    cin >> x;
    // 确定边界值
    double l = -100000, r = 100000;
    // 注意循环条件处理精度问题
    while (r - l > 1e-8) 
    {
        // 步骤 A: 找中间值
        double mid = (l + r) / 2;
        // 步骤 B: 判断
        if (mid * mid * mid < x) l = mid;
        else r = mid;
    }
    printf("%.6f", r);
    return 0;
}

题目三解析

输入一个长度为 n 的整数序列。

接下来再输入 m个询问,每个询问输入一对 l,r。

对于每个询问,输出原序列中从第 l个数到第 r个数的和。

输入格式

第一行包含两个整数 n和 m。

第二行包含 n个整数,表示整数数列。

接下来 m行,每行包含两个整数 l 和 r,表示一个询问的区间范围。

输出格式

共 m行,每行输出一个询问的结果。

数据范围

1 ≤l ≤ r ≤ n,

1 ≤ n,m ≤ 100000,

−1000≤数列中元素的值≤1000

输入样例:

5 3

2 1 3 6 4

1 2

1 3

2 4

输出样例:

3

6

10

算法原理

本题用到了前缀和的知识:

什么是前缀和?

数列的和时,Sn = a1+a2+a3+…an; Sn就是数列的前 n 项和。

前缀和就是新建一个数组,新建数组中保存原数组前 n 项的和。

前缀和有什么用?

快速求某个区间中所有元素的加和。

例 S4 = a1 + a2 + a3 + a4; S1 = a1。所以可以通过 S4-S1 得到 a2+a3+a4 的值。

代码实现

#include <iostream>
using namespace std;
const int N = 100010;
int a[N];//保存原数组
int s[N];//保存前缀和
int main()
{
    int n, m;
    cin >> n >> m;
    //从a[1]开始保存。a[0]是0
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    s[0] = 0;
    //计算前缀和
    for(int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + a[i];
    for(int i = 0; i < m; ++i)
    {
        int l, r;//保存区间
        cin >> l >> r;
        //s[r] = a[1]+ ··· + a[r]
        //s[l - 1] = a[1]+ ··· + a[l - 1]
        //s[r] - s[l - 1] = a[l] + ··· + a[r]
        cout << s[r] - s[l - 1] << endl;
    }
}

题目四解析

输入一个 n 行 m列的整数矩阵,再输入 q个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 n,m,q

接下来 n行,每行包含 m个整数,表示整数矩阵。

接下来 q行,每行包含四个整数 x1,y1,x2,y2,表示一组询问。

输出格式

共 q 行,每行输出一个询问的结果。

算法原理

一步一步学会二维前缀和的推导

给出一个二维数组,在给出一个子数组的左上角坐标、右下角坐标,求出子数组中的所有元素的和。

用s[i,j]表示(1,1)~(i,j)的和。

先看看s[i,j]怎么求:

s[1,1] = a[1,1]
s[1,2] = a[1,1] + a[1,2]
       = s[1,1] + a[1,2]
s[1,3] = a[1,1] + a[1,2] + a[1,3] 
       = s[1,2] + a[1,3] 
s[2,1] = a[1,1] + a[2,1] 
       = s[1,1] + a[2,1] 
s[2,2] = a[1,1] + a[1,2] + a[2,1] +  a[2,2] 
       = s[1,2] + s[2,1] - s[1,1] + a[2, 3] 
s[2,3] = a[1,1] + a[1,2] + a[1,3] + a[2,1] + a[2,2] + a[2,3] 
       = s[1,3] + s[2,2] - s[1,2] + a[2, 3]

可以得到一下公式:

s[i,j] = s[ i−1,j ]+ s [ i , j−1 ] - s[ i−1, j−1 ]+ a[ i ][ j ]

也就是,可以在o(n2)的时间复杂度内求出所有s

当求出 s,求 (x1,y1)~(x2,y2)的和

如图所示:黄色部分 = 紫色框 - 蓝色框 - 红色框 + 黑色框。

也就是:

所以当求出 s 后,就能在 o(1)的时间复杂度内,求出子矩阵的和。

所以总时间复杂度是:o(n2)

#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int s[N][N];
int m, n, q;
int main(){
  cin >> n >> m >> q;
  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j <=m; j++)
    {
      cin >> a[i][j];
    }
  }
  // 求 s[i, j]
  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j <=m; j++)
    {
      s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    }
  }
  while(q > 0)
  {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    // 求子矩阵和
    cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
    q --;
  }
}

题目五解析

算法原理

算法一(贪心)

题意:就是要我们找到最小值让机器人可以达到终点

我们先看一组样例:3 4 3 2 4

要想它最小,我们可以直接从最后面开始运算,初始化他的代价为0,我们设初值为x

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int num[N];
int n;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>num[i];
    int res = 0;
        for(int i = n - 1; i >= 0; i--)
        {
            if((num[i] + res) % 2 == 0)
                res = (num[i] + res) / 2;
            else
                res = (num[i] + res) / 2 + 1;
        }
    cout<<res<<endl;
}

算法二:容器

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i)
        cin >> v[i];
    int res = 0;
    for (int i = n-1; i >= 0; i--) 
    {
        if((v[i] + res) % 2 == 0)
                res = (v[i] + res) / 2;
            else
                res = (v[i] + res) / 2 + 1;
    }
    cout << res << endl;
    return 0;
}

题目六解析

四平方和定理,又称为拉格朗日定理:

每个正整数都可以表示为至多 4个正整数的平方和。

如果把 0包括进去,就正好可以表示为 4个数的平方和。

比如:

5=02+02+12+22

7=12+12+12+22

对于一个给定的正整数,可能存在多种平方和的表示法。

要求你对 4个数排序:

0 ≤ a ≤ b ≤ c ≤ d

并对所有的可能表示法按 a,b,c,d为联合主键升序排列,最后输出第一个表示法。

输入格式

输入一个正整数 N。

输出格式

输出4个非负整数,按从小到大排序,中间用空格分开。

数据范围

0<N<5∗106

输入样例:

5

输出样例:

0 0 1 2

算法原理

根据题意,直接四重循环暴力枚举a,b,c,d,意料之中的超时了,后来慢慢优化,优化成三重循环,仍然不行(当时没有理解清楚到 a <= b<= c<= d这个关系),再然后,就想到了打表

  1. 建立哈希表,存储小于n的数c,假设e = c^2 + d^2,则h[e] = c,从小到大遍历c, d只存储先出现的(因为字典序小)
  2. 从小到大遍历a、b,查找1中建立的哈希表,若 h[n - a^2 - b^2]存在,则算出d,

代码实现

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e8 + 10;
int h[N];
int main() 
{
    int n;
    cin >> n;
    //打表,找出1 - n,所有完全平方数两两之和,如果存在只记第一次出现(题目要求找出字典序小的)
    for (int i = 0; i * i * 2<= n; i++) 
    {
        for (int j = i; j * j + i * i <= n; j++) 
        {
            if (!h[i * i + j * j])
                h[i * i + j * j] = i + 1;//防止i = 0时在后面判断查找跳过 i = 0的情况
        }
    }
    //0<= a <= b <= c <= d,可以得出a^2 <= n / 4, a^2 + b^ 2 <= n / 2; 
    for (int i = 0; i * i * 4 <= n; i++) 
    {
        for (int j = i; j * j + i * i <= n / 2; j++) {
            int t = n - i * i - j * j;
            if (h[t]) 
            {
                int c = h[t] - 1;   
                //防止开根号后因为精度关系,向下取整,例:25 开根号得到4.99999向下取整为4;
                int d = (sqrt(t - c * c) + 1e-4);
                printf("%d %d %d %d", i, j, c, d);
                return 0;
            }
        }
    }
    return 0;
}

题目七解析

儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N块巧克力,其中第 i块是 Hi×Wi的方格组成的长方形。

为了公平起见,小明需要从这 N块巧克力中切出 K块巧克力分给小朋友们。

切出的巧克力需要满足:

形状是正方形,边长是整数大小相同

例如一块 6×5的巧克力可以切出 6

块 2×2 的巧克力或者 2块 3×3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?

输入格式

第一行包含两个整数 N和 K。

以下 N行每行包含两个整数 Hi和 Wi。

输入保证每位小朋友至少能获得一块 1×1

的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

数据范围

1≤N,K≤105,

1≤Hi,Wi≤105

输入样例:

2 10

6 5

5 6

输出样例:

2

算法原理

思路:

小巧克力边长 a 一定在 1 – 100000 之间

答案即为:在 1 – 100000 之间找到一个最大的数,使得所有的 (w[i]/a) * (h[i]/a) 之和大于要求的数量 k。

使用二分法找到 a 的最大取值即为答案。

代码实现

#include <iostream>
using namespace std;
int const N = 100010;
int w[N], h[N];//存储长、宽
int n, k;
bool chack(int a)
{
  int num = 0;//记录分成长度为 a 的巧克力数量
  for (int i = 0; i < n; i++)
  {
    num += (w[i] / a) * (h[i] / a);//每一大块可以分成的边长为 a 的巧克力数量
    if (num >= k) return true;//大于要求数量,返回真
  }
  return false;
}
int main()
{
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> h[i] >> w[i];
  int l = 1, r = 1e5;//小巧克力数量边长一定在 1 -- 100000 之间
  while (l < r)//二分小巧克力边长范围,找到符合要求的最大值
  {
    int mid = l + (r - l + 1 >> 1);//因为l = mid ,所以 mid 取 l + r + 1 >> 1,为了防止加和越界,改写成 l + (r - l + 1 >> 1)
    if (chack(mid)) l = mid;
    else r = mid - 1;
  }
  cout << r;
}

题目八解析

地图上有 N个目标点,用整数 Xi,Yi表示目标在地图上的位置,每个目标都有一个价值 Wi

注意:不同目标可能在同一位置。

现在有一种新型的激光炸弹,可以摧毁一个包含 R×R个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和 x,y轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 N和 R,分别代表地图上的目标数目和正方形包含的横纵位置数量,数据用空格隔开。

接下来 N 行,每行输入一组数据,每组数据包括三个整数 Xi,Yi,Wi,分别代表目标的 x 坐标,y坐标和价值,数据用空格隔开。

输出格式

输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。

算法原理

代码实现

//
// Created by Genes on 2020/12/2.
//
// 激光炸弹
#include <algorithm>
#include <iostream>
#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)
using namespace std;
const int N = 5e3 + 10; //不能开 1e5+10, 内存限制比较严格
int s[N][N];
int n, r;
int main() {
    ios;
    cin >> n >> r;
    r = min(5001, r); // 因为r最大可以取 10^9
    for (int i = 0; i < n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
//        s[++x][++y]=w;  //错误
        s[++x][++y] += w; //右移一位, 就不需要考虑边界了, 并且必须是+=, 不能是=, 因为1个位置可能有多个目标
    }
    for (int i = 1; i <= 5001; i++) {
        for (int j = 1; j <= 5001; j++) {
//            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = r; i <= 5001; i++) {
        for (int j = r; j <= 5001; j++) {
            ans = max(ans, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
        }
    }
    cout << ans << endl;
    return 0;
}

题目九解析

给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K的倍数,我们就称这个区间 [i,j]是 K倍区间。

你能求出数列中总共有多少个 K倍区间吗?

输入格式

第一行包含两个整数 N 和 K。

以下 N

行每行包含一个整数 Ai

输出格式

输出一个整数,代表 K倍区间的数目。

算法原理

思路:一眼看去我们就可以知道这个算法用的前缀和,

分析:

求区间[l,r]的和是k的倍数的个数。求区间和,我们可以通过前缀和来求出。我们规定sum[i]表示第1个元素到第i个元素的和。那么sum[r] - sum[l-1]就是区间[l,r]的和。区间[l,r]的和是k的倍数即(sum[r] - sum[l-1])%k == 0 即sum[r]%k == sum[l-1]%k

如果你觉得文字难以理解,那么看图:

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long ll;
int sum[N],a[N],res[N];
int n,k;
ll ans=0;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=(sum[i-1]+a[i])%k;//前缀和取模
        ans+=res[sum[i]];//更新答案  
        res[sum[i]]++;//两个相等的前缀和就能组成一个k倍区间
    }
    cout<<ans+res[0]<<endl;
    return 0;
}
相关文章
|
6月前
【每日一题Day149】LC2389和有限的最长子序列 | 贪心+前缀和+二分查找
【每日一题Day149】LC2389和有限的最长子序列 | 贪心+前缀和+二分查找
43 0
|
移动开发 算法 机器人
[蓝桥杯] 二分与前缀和习题练习
又来更新了。二分与前缀和是蓝桥杯比较常考的内容,所以我们要多加练习这方面的习题。二分与前缀和的难度相对来说不算大,我们应该掌握其关键要点。
106 0
|
5月前
【洛谷 P1873】[COCI 2011_2012 #5] EKO _ 砍树 题解(向量+二分查找)
【COCI 2011/2012 #5】EKO 砍树问题摘要: - 伐木工Mirko需砍$M$米木材,只能砍一排树,使用二分搜索策略确定锯片最大高度$H$。 - 锯片设为$H$米时,会砍掉所有高于$H$的树顶,求得所需木材至少$M$米的最高$H$。 - 输入:树的数量$N$和所需木材总长$M$,每棵树的高度。 - 输出:锯片的最大高度。
41 0
|
6月前
【错题集-编程题】最长上升子序列(二)(贪心 + 二分)
【错题集-编程题】最长上升子序列(二)(贪心 + 二分)
|
6月前
leetcode代码记录(动态规划基础题(斐波那契数列)
leetcode代码记录(动态规划基础题(斐波那契数列)
32 0
|
6月前
|
算法
算法思想总结:前缀和算法
算法思想总结:前缀和算法
|
6月前
|
算法
【数据结构与算法】常用算法 前缀和
【数据结构与算法】常用算法 前缀和
|
存储 算法
算法:图解前缀和问题
算法:图解前缀和问题
|
SQL 人工智能 开发框架
线段树模板+例题
线段树模板+例题
77 1
|
人工智能 算法 JavaScript
[数据结构与算法]基础算法(排序, 二分, 前缀, 差分)
快速排序:(分治的思想)✅ 确定分界点:q[l], q[(r+l)/2], q[r] (中间点可以随机选, 按照同一规则, 这里选(l+r)/2该点) 维护数组:维护分界点的左边都比分界点小,分界点的右边都比分界点大 按照维护关系, 递归处理左右两段 💡思想解释: 先整后细:先让大体总的符合条件,再部分部分解决