蓝桥杯第三讲--二分【习题】

举报
辰chen 发表于 2022/06/14 23:56:18 2022/06/14
【摘要】 文章目录 前言机器人跳跃问题题目要求思路分析代码 四平方和题目要求思路分析1代码1思路分析2代码2思路分析3代码3 分巧克力题目要求思路分析代码 前言 蓝桥杯官网：蓝桥杯大赛—...

文章目录

前言

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第三讲：二分【习题】

二分算法的模板见博文：二分算法模板
二分【例题】详见博客：蓝桥杯第三讲–二分【例题】

本篇博客所包含习题有：
👊机器人跳跃问题
👊四平方和
👊分巧克力

博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！

机器人跳跃问题

本题来源：今日头条2019，笔试题

题目要求

题目描述：

机器人正在玩一个古老的基于 DOS 的游戏。

游戏中有 N+1 座建筑——从 0 到 N 编号，从左到右排列。

编号为 0 的建筑高度为 0 个单位，编号为 i 的建筑高度为 H(i) 个单位。

起初，机器人在编号为 0 的建筑处。

每一步，它跳到下一个（右边）建筑。

假设机器人在第 k 个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1 个建筑。

如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1) 的能量值。

游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式：

第一行输入整数 N。

第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N) 代表建筑物的高度。

输出格式：

输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围：

1 ≤ N, H(i) ≤ 105

输入样例1：

5
3 4 3 2 4

输出样例1：

4

输入样例2：

3
4 4 4

输出样例2：

4

输入样例3：

3
1 6 4

输出样例3：

3

思路分析

假设某一时刻（在第 k 个建筑上的时候）能量为 E，且 H(k+1)>E，那么在跳跃到第 k+1 个建筑后，剩余能量为：E-(H(k+1)−E)=2E-H(k+1)；若有H(k+1)<E，那么在跳跃到第 k+1 个建筑后，剩余能量为：E+(E−H(k+1))=2E-H(k+1)。综上可以看出，不管 H(k+1) 和此时能量E有怎样的关系，必然有在跳跃到 k+1 建筑时有剩余能量为：2E-H(k+1)，不难知道，假设初始能量的最小值为 E0，那么对于任何 Ei > E0，必然是可以跳到最后一个建筑，故我们可以采用二分的做法，找到 E0，故我们可以设 l = 1，然后来考虑 r 的范围，我们在跳跃的过程中要求自身的能量必须 >=0，那么我们来找一找能量的上界：假设 hmax为 h数组中的最大值，那么若此时的能量 E >= hmax，那么就有 2E - hmax >= hmax，即我们的 E 如果一旦比 hmax 要大，就肯定满足题目要求，故我们可以设 r = hmax.

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int h[N];
int n, hmax;

bool check(int e)
{
    for (int i = 0; i < n; i ++ ) 
    {
        e = 2 * e - h[i];
        if (e >= hmax) return true;
        if (e < 0) return false;
    }
    
    return true;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) 
    {
        scanf("%d", &h[i]);
        if (hmax < h[i])
            hmax = h[i];
    }
        
    int l = 1, r = hmax;
    while (l < r)
    {
        int mid = l + r >> 1;   
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    printf("%d\n", l);
    
    return 0;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    • 
  
  • 33
    • 
  
  • 34
    • 
  
  • 35
    • 
  
  • 36
    • 
  
  • 37
    • 
  
  • 38
    • 
  
  • 39
    • 
  
  • 40
    • 
  
  • 41
    • 
  
  • 42
    • 
  
  • 43
    • 
  
  • 44
    • 
  
  • 45
    •

四平方和

本题来源：第七届蓝桥杯省赛C++A/B组,第七届蓝桥杯省赛JAVAB/C组

题目要求

题目描述：

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多 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

思路分析1

蓝桥杯嘛，又名“暴力杯”，这个题就很典型了，暴力运行速度比二分和哈希还快，离大谱，本题要求还是很直白的，唯一的地方就是在于要求按 a,b,c,d 为联合主键升序排列，即 a <= b <= c <= d，故我们在暴力枚举的时候，a 从 0 开始枚举，b 从 a 开始枚举，c 从 b 开始枚举，不需要枚举 d，去判断 d 是否合法即可，判断 d 是否合法就是看 d 开平方后再平方是否和 d值一致，如果一致就输出 a b c d 序列，并结束程序。

代码1

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    
    for (int a = 0; a * a <= n; a ++ )
        for (int b = a; a * a + b * b <= n; b ++ ) 
            for (int c = b; a * a + b * b + c * c <= n; c ++ ) 
            {
                int t = n - (a * a + b * b + c * c);
                int d = sqrt(t);
                if (d * d == t)
                {
                    printf("%d %d %d %d\n", a, b, c, d);
                    exit(0);
                }
            }
            
    return 0;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    •

思路分析2

我们对暴力进行优化，我们可以先枚举两维：枚举 c 和 d，把 c 和 d 的所有情况全部存储到一个数组之中（存储 c2 + d2，c，d），然后再枚举 a 和 b 的时候，计算 a2 + b2，对于每一个计算出来的 a2 + b2，我们都去数组中比对是否有一个c2 + d2使得 a2 + b2 + c2 + d2 = n，如果有，就输出 a b c d 序列然后退出程序，因为我们要在数组中寻找是否有符合条件的c2 + d2，故我们可以给数组排序后二分查找，所以我们要重载小于号：重载规则为c2 + d2小的排在前面，然后在遍历 a 和 b 之前给数组排序，现在我们还是来考虑 a <= b <= c <= d 这个问题，我们的 a 和 b可以在枚举的时候采取暴力法中的那样 a 从 0 开始，b 从 a 开始，且我们枚举 c 和 d 按照暴力的方式同样可以保证 c <= d，然后我们重载小于号时，可以让 c2 + d2 的大小作为第一排序条件，然后按照 c 的大小排序，然后按照 d 的大小排序，这样就可以保证 在 c2 + d2 相同的时候保证 c 更小的排在更前面。此时我们保证了 a<= b ，c <= d，现在来求证：b <= c：因为我们的 a 和 b 是从小到大进行枚举的，且对于每一种情况我们都去判断是否有符合条件的 c 和 d，因为 a2 + b2 + c2 + d2 = n，故在 a 和 b 都是很小数的情况下，要想 四平方和为以定值，c 和 d 必然是一个大数，即能保证 b <= c，证毕。

代码2

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 5000010;

struct Sum
{
    int s, c, d;
    bool operator < (const Sum &t) const
    {
        if (s != t.s) return s < t.s;
        if (c != t.c) return c < t.c;
        if (d != t.d) return d < t.d;
    }
}sum[N];

int main()
{
    int n;
    scanf("%d", &n);
    
    int m = 0;
    for (int c = 0; c * c <= n; c ++ ) 
        for (int d = c; c * c + d * d <= n; d ++ ) 
            sum[m ++] = {c * c + d * d, c, d};
            
    sort(sum, sum + m);
    
    for (int a = 0; a * a <= n; a ++ ) 
        for (int b = a; a * a + b * b <= n; b ++ )
        {
            int t = n - (a * a + b * b);
            int l = 0, r = m;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (sum[mid].s >= t) r = mid;
                else l = mid + 1;
            }
            // 判断一下是否真的找到了
            if (sum[l].s == t)
            {
                printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
                exit(0);
            }
        }
        
    return 0;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    • 
  
  • 33
    • 
  
  • 34
    • 
  
  • 35
    • 
  
  • 36
    • 
  
  • 37
    • 
  
  • 38
    • 
  
  • 39
    • 
  
  • 40
    • 
  
  • 41
    • 
  
  • 42
    • 
  
  • 43
    • 
  
  • 44
    • 
  
  • 45
    • 
  
  • 46
    • 
  
  • 47
    • 
  
  • 48
    • 
  
  • 49
    • 
  
  • 50
    • 
  
  • 51
    • 
  
  • 52
    •

思路分析3

思路三其实就是思路二的另一种形式，我们思路二去查找的时候采取的是二分的查找方法，我们还可以采用哈希表去查找，在将 {c2 + d2，c，d} 存入哈希表前，判断是否表中已经有 c2 + d2 这样的值，因为我们的 c 和 d 是从小到大枚举的，因此先算到的 c2 + d2 肯定是优于后算到的 c2 + d2，哈希表使用的是 C++ 中的库，具体操作可查看博文：STL—map，unordered_map 和 map 用法是一致的，手写哈希表见博文：哈希表

代码3

注：蓝桥杯官网不能使用 unordered_map，但是代码思路无任何问题，正式比赛可以使用！

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

unordered_map<int, PII> res;

int main()
{
    int n;
    scanf("%d", &n);
    
    for (int c = 0; c * c <= n; c ++ )
        for (int d = c; c * c + d * d <= n; d ++ )
        {
            int t = c * c + d * d;
            if (!res.count(t))
                res[t] = {c, d};
        }
    
    for (int a = 0; a * a <= n; a ++ ) 
        for (int b = a; a * a + b * b <= n; b ++ ) 
        {
            int t = n - (a * a + b * b);
            if (res.count(t))
            {
                printf("%d %d %d %d\n", a, b, res[t].x, res[t].y);
                exit(0);
            }
        }
        
    return 0;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    • 
  
  • 33
    • 
  
  • 34
    • 
  
  • 35
    • 
  
  • 36
    • 
  
  • 37
    • 
  
  • 38
    • 
  
  • 39
    • 
  
  • 40
    •

分巧克力

本题来源：第八届蓝桥杯省赛C++A/B组,第八届蓝桥杯省赛JAVAA/B组

题目要求

题目描述：

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

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

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

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

切出的巧克力需要满足：

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

例如一块 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

思路分析

假设分得的正方形巧克力的边长为 m，那么对于一块长为 Hi，宽为 Wi 的巧克力，其可以被分为：(Hi / m) * (Wi / m)块，我们知道，分得巧克力的边长和巧克力被拆成的块数是成反比的，即边长越长，分得的块数越少，我们的目标是在可以分成 k 块的前提下，使得边长更大，故我们可以用二分求解

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int h[N], w[N];
int n, k;

bool check(int u)
{
    int sum = 0;
    for (int i = 0; i < n; i ++ ) 
    {
        int t = (h[i] / u) * (w[i] / u);
        sum += t;
        if (sum >= k) return true;
    }
    
    return false;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) 
        scanf("%d%d", &h[i], &w[i]);
        
    int l = 1, r = 1e5;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    
    printf("%d\n", l);
    
    return 0;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    • 
  
  • 33
    • 
  
  • 34
    • 
  
  • 35
    • 
  
  • 36
    • 
  
  • 37
    • 
  
  • 38
    • 
  
  • 39
    • 
  
  • 40
    • 
  
  • 41
    • 
  
  • 42
    •

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/122583508

【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据结构 机器人
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入