第十四届蓝桥杯程序设计C++B组 (详细图解+保姆级注释)

0.写在前面：

本届CB组题目难度较往年整体提升了一些，考察知识点全面，题目质量很高，推荐备赛蓝桥杯或感兴趣的同学深入研究本套题，废话不多说，直接上干货！

一.冶炼金属 (签到题难度，考察数论分块知识or二分)

有部分同学可能知道下取整的定义，但是对其性质不够了解，从而导致无法快速推出公式

不过没有关系~~，二分查找也是可以的！

题目分析：

 注意：下方参考代码中的二分模板使用的是左开右开写法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, mi, ma = 2e9; //初始化

int main()
{
    cin >> n;
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int l = -1, r = 1e9 + 1;
        while(l + 1 < r)
        {
            int mid = l + r >> 1;
            if(a / mid > b) l = mid;
            else r = mid;
        }
        mi = max(mi, r);  //最小值要取到最大
        
        l = -1, r = 1e9 + 1;
        while(l + 1 < r)
        {
            int mid = l + r >> 1;
            if (a / mid >= b) l = mid;
            else r = mid;
        }
        ma = min(ma, l); //最大值要取到最小
    }
    cout << mi << " " << ma << endl;
    
    return 0;
}

方法二：推公式法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, mi, ma = 2e9;

int main()
{
    cin >> n;
    while(n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        mi = max(mi, a / (b + 1) + 1);
        ma = min(ma, a / b);
    }
    cout << mi << " " << ma << endl;
    
    return 0;
}

二.飞机降落（状态压缩DP or DFS)

考场上用贪心做法的同学要好好反思了，做题的第一步是根据数据范围推测算法

若为贪心做法数据范围应该在100000左右，而本题数据最大为10，故首选状态压缩DP

或者DFS，不过贪心写得好也是可以拿到一部分分数的~~~      下面讲解贪心做法