[第二章]二分与前缀和-阿里云开发者社区

题目一解析

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

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

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

输入格式

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

第二行包含n个整数（均在1~10000范围内），表示完整数组。

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

输出格式

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

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

数据范围

1≤n≤100000

1≤q≤10000

1≤k≤10000

样例

输入样例：

6 3

1 2 2 3 3 4

输出样例：

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

输出样例：

算法原理

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

什么是前缀和？

数列的和时，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(n²)的时间复杂度内求出所有s

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

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

也就是：

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

所以总时间复杂度是：o(n²)

#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=0²+0²+1²+2²

7=1²+1²+1²+2²

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

要求你对 4个数排序：

0 ≤ a ≤ b ≤ c ≤ d

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

输入格式

输入一个正整数 N。

输出格式

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

数据范围

0<N<5∗106

输入样例：

输出样例：

0 0 1 2

算法原理

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

建立哈希表，存储小于n的数c,假设e = c^2 + d^2,则h[e] = c,从小到大遍历c, d只存储先出现的(因为字典序小)
从小到大遍历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块是 H_i×W_i的方格组成的长方形。

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

切出的巧克力需要满足：

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

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

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

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

输入格式

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

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

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

的巧克力。

输出格式

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

数据范围

1≤N,K≤10⁵,

1≤H_i,W_i≤10⁵

输入样例：

2 10

6 5

5 6

输出样例：

算法原理

思路：

小巧克力边长 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个目标点，用整数 X_i,Y_i表示目标在地图上的位置，每个目标都有一个价值 W_i。

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

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

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

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

输入格式

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

接下来 N 行，每行输入一组数据，每组数据包括三个整数 X_i,Y_i,W_i，分别代表目标的 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 的数列，A₁,A₂,…A_N，如果其中一段连续的子序列 A_i,A_i+1,…A_j 之和是 K的倍数，我们就称这个区间 [i,j]是 K倍区间。

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

输入格式

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

以下 N

行每行包含一个整数 A_i。

输出格式

输出一个整数，代表 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;
}

[第二章]二分与前缀和

题目一解析

算法原理

代码实现

题目二解析

算法原理

代码实现

题目三解析

算法原理

代码实现

题目四解析

算法原理

题目五解析

算法原理

代码实现

题目六解析

算法原理

代码实现

题目七解析

算法原理

代码实现

题目八解析

算法原理

代码实现

题目九解析

算法原理

代码实现

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

[第二章]二分与前缀和

题目一解析

算法原理

代码实现

题目二解析

算法原理

代码实现

题目三解析

算法原理

代码实现

题目四解析

算法原理

题目五解析

算法原理

代码实现

题目六解析

算法原理

代码实现

题目七解析

算法原理

代码实现

题目八解析

算法原理

代码实现

题目九解析

算法原理

代码实现

热门文章

最新文章

相关电子书