8.1训练课

二分查找

左侧边界

// 定义左右边界 l 和 r
int l = 0,r = n + 1,ans = -1;
// 使用二分查找算法查找值 x
while(l+1<r)
{
  // 计算中间位置
  int mid = (l+r)/2;
  // 如果中间位置的值小于 x，调整左边界
  if(a[mid] < x)
  {
     l = mid;
  }
  // 否则调整右边界
  else
  {
    r = mid;
  }	
}

右侧边界

// 定义左右边界 l 和 r
int l = 0, r = n + 1, ans = -1;
// 使用二分查找算法查找值 x
while(l + 1 < r)
{
    // 计算中间位置
    int mid = (l + r) / 2;
    // 如果中间位置的值大于 x，调整右边界
    if(a[mid] > x)
    {
        r = mid;
    }
    // 否则调整左边界
    else
    {
        l = mid;
    }
}

核心原理
当求解的目标具有有序性时，可使用二分算法。先根据待查找区间中点位置，判断结果会在左侧还是右侧，然后舍弃一半的查找区间，在结果存在的区间继续进行二分查找 。

P6568 [NOI Online #3 提高组] 水壶

错因，时间不足

首先读取两个整数 n 和 k，n 代表总倒水次数，k 代表连续倒水次数；接着读取 n 个整数，代表每次倒水的水量。之后计算前缀和数组 sum，sum[i] 表示前 i 次倒水的总水量。遍历所有长度为 k 的连续倒水区间，利用前缀和公式 sum[i + k - 1] - sum[i - 1] 快速计算每个区间的总水量，并找出其中的最大值。最后输出这个最大值，即为连续 k 次倒水的最大水量。

#include<bits/stdc++.h> 
using namespace std;
// 定义数组 a 用于存储输入的数组元素，sum 用于存储前缀和
int a[1010101],sum[1010101];

int main()
{
    // n 表示数组长度，k 表示连续水壶里的水的总和
    int n,k;
    // 读取输入的 n 和 k
    cin>>n>>k;
    // 读取数组元素，下标从 1 开始
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    // 计算前缀和数组，sum[i] 表示前 i 个元素的和
    for(int i = 1;i<=n;i++)
    {
        sum[i] = sum[i-1]+a[i];
    }
    // ans 用于记录最大的长度为 k 的连续水壶里的水的总和，初始化为 0
    int ans = 0;
    // 遍历所有可能的长度为 k 的连续水壶里的水的总和
    for(int i = k+1;i<=n;i++)
    {
        // 计算当前长度为 k 的水的总和
        int s = sum[i] - sum[i-k-1];
        // 更新最大和
        ans = max(ans,s);
    }
    // 输出最大和
    cout<<ans;
    return 0;
}

P5594 【XR-4】模拟赛

错因，时间不足

本题是要计算 X 校 CSP 校内集训期间，教练每天需要准备的模拟赛场数。已知有 n 名 OIer 参与集训，教练准备了 m 套模拟赛题，每名 OIer 在接下来 k 天里有 m 天有空打模拟赛，且需按顺序完成这 m 套题，若同一天多人打同一套题，教练只需准备一场。解题思路是先读取参与集训的人数 n、模拟赛题套数 m 和总天数 k，再读取每名 OIer 打每套模拟赛的日期。之后借助一个二维数组来记录每天需要准备哪些套题，数组的行代表日期，列代表模拟赛题的套数，若某天需要准备某套题，就在对应位置做标记。最后，遍历每一天，统计当天需要准备的模拟赛题套数，即对应该天的数组行里有标记的元素数量，将这个数量输出，按顺序输出每天的结果，就能得到教练每天需要准备的模拟赛场数。

#include<bits/stdc++.h>
using namespace std;
// 二维数组 a 用于记录第 i 天是否需要准备第 j 套模拟赛题
int a[1010][1010];

int main()
{
    // n 表示参与集训的人数，m 表示模拟赛题套数，k 表示天数
    int n,m,k;
    // 读取输入的 n, m, k
    cin>>n>>m>>k;
    // 遍历每个人的日程安排
    for(int i = 1;i<=n;i++)
    {
        // 遍历每个人需要打的模拟赛题
        for(int j = 1;j<=m;j++)
        {
            int x;
            // 读取第 i 个人第 j 次打模拟赛的日期
            cin>>x;
            // 标记第 x 天需要准备第 j 套模拟赛题
            a[x][j] = 1;
        }
    }
    // 遍历每一天
    for(int i = 1;i<=k;i++)
    {
        // ans 用于记录第 i 天需要准备的模拟赛场数
        int ans = 0;
        // 遍历所有模拟赛题套数
        for(int j = 1;j<=m;j++)
        {
            // 如果第 i 天需要准备第 j 套模拟赛题
            if(a[i][j] != 0)
            {
                // 当天需要准备的场数加 1
                ans++;
            }
        }
        // 输出第 i 天需要准备的模拟赛场数，并添加一个空格
        cout<<ans<<" ";
    }
    // 原代码缺少返回语句，为保证代码规范性，这里补充
    return 0;
}

P12176 [蓝桥杯 2025 省 Python B] 书架还原

错因，时间不足

本题要计算将错乱书架上的书恢复到按编号从小到大排列所需的最少交换次数，采用贪心算法解决。

首先读取书的总数 n 和每本书当前编号，用数组 mp 记录每本书的位置，方便快速查找。接着初始化交换次数 ans 为 0。从第一个位置开始遍历，检查当前位置 i 的书编号是否为 i。若不是，说明位置不对，需要交换。先更新 mp 数组里错误编号书的位置，再将位置 i 的书和编号为 i 的书交换，每次交换后 ans 加 1。

遍历结束后，所有书都回到正确位置，此时输出 ans 就是最少交换次数。该方法每次操作都让一本书回到正确位置，保证交换次数最少。

#include<bits/stdc++.h>  // 包含所有标准库的头文件
using namespace std;
int a[1010101];  // 数组 a 用于存储当前书架上每本书的编号，索引从 1 开始
int mp[1010101];  // 数组 mp 用于记录每本书当前所在的位置，键为书的编号，值为位置
int main()
{
    int n;  // 定义变量 n 用于存储书架上书的总数
    cin>>n;  // 读取书的总数
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];  // 读取当前书架上第 i 个位置的书的编号
        mp[a[i]] = i;  // 记录编号为 a[i] 的书当前所在的位置为 i
    }
    int ans = 0;  // 定义变量 ans 用于记录最少交换次数，初始化为 0
    for(int i = 1;i<=n;i++)
    {
        if(a[i] != i)  // 如果第 i 个位置上的书编号不是 i，说明需要交换
        {
            mp[a[i]] = mp[i];  // 更新编号为 a[i] 的书的位置为当前 i 位置上书的位置
            swap(a[i],a[mp[i]]);  // 交换第 i 个位置和编号为 i 的书所在位置的书
            ans++;  // 交换次数加 1
        }
    }
    cout<<ans;  // 输出最少交换次数
    return 0;
}