P1678 烦恼的高考志愿

首先读取参考值数量 $n$和查询次数$t$，把 $n$ 个参考值存入数组 $a$。接着对数组 $a$ 排序，使其升序排列，为二分查找做准备。为避免边界问题，在数组开头和末尾分别设置极小值 $-1e6 - 1$ 和极大值 $2e6$。对于每个查询值 $x$，使用二分查找来定位。初始化左右边界 $l = 0$ 和 $r = n + 1$，在 $l + 1 < r$ 的循环里，计算中间位置 $mid$，依据 $a[mid]$ 与 $x$的大小关系更新边界。循环结束后，$l$ 和$ r $相邻，$a[l]$ 小于 $x$，$a[r]$ 大于等于 $x$。比较 $a[l]$ 和 $a[r]$ 与$ x $的差值绝对值，取较小值累加到结果$ ans $里。处理完所有查询后，输出$n$个离$x$最近数之和$ans$。

#include<bits/stdc++.h> 
using namespace std;
const int MAXN = 10101010; // 定义数组最大长度
int a[MAXN]; // 存储输入的数组

int main()
{
    int n, t; // n 表示数组元素个数，t 表示查询次数
    cin >> n >> t; // 读取 n 和 t
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i]; // 读取数组元素
    }
    long long ans = 0; // 用于存储最终结果，使用 long long 防止溢出
    sort(a + 1, a + n + 1); // 对数组进行排序，排序范围是从 a[1] 到 a[n]
    a[0] = -1e6 - 1; // 在数组开头添加一个极小值，方便后续二分查找
    a[n + 1] = 2e6; // 在数组末尾添加一个极大值，方便后续二分查找
    while(t--)
    {
        int x; // 存储当前查询的值
        cin >> x; // 读取查询值
        int l = 0, r = n + 1; // 初始化二分查找的左右边界
        while(l + 1 < r) // 二分查找，直到左右边界相邻
        {
            int mid = (l + r) / 2; // 计算中间位置
            if(a[mid] < x) // 如果中间元素小于查询值
            {
                l = mid; // 左边界更新为 mid
            }
            else
            {
                r = mid; // 右边界更新为 mid
            }
        }
        // 取左右边界对应元素与查询值差值的最小值累加到结果中
        ans += min(abs(a[l] - x), abs(a[r] - x));
    }
    cout << ans; // 输出最终结果
    return 0;
}

P3984 高兴的津津

本题要计算津津在一系列比赛获奖后累计开心的总天数。津津每次拿到 $Au$ 后开心会持续 $T$ 天，若在开心期间再次获奖，开心时间会从新获奖日起重新计算$ T$ 天。先读取比赛场数$ n$ 和每次开心持续天数$ T$，再读取$ n$ 个单调递增的日期，表示获奖时间。初始化总开心天数为第一次获奖后的开心天数 $ T$。接着遍历除最后一次外的每次获奖，比较相邻两次获奖的时间间隔和 $T$ 的大小。若间隔小于 $T$，说明上一次开心期还未结束就再次获奖，新增开心天数就是间隔天数；若间隔大于等于 $T$，则新增开心天数为 $T$。

#include<bits/stdc++.h>  
using namespace std;    
int a[1010101];         // 定义数组 a，用于存储每次获奖的日期，数组大小足够大以满足数据范围

int main()
{   
    int n, t;           // 定义两个整型变量，n 表示比赛场数，t 表示每次获奖后开心持续的天数
    cin >> n >> t;      // 从标准输入读取 n 和 t 的值
    for(int i = 1; i <= n; i++)  // 循环读取 n 次，获取每次获奖的日期
    {   
        cin >> a[i];    // 将每次获奖的日期存储到数组 a 中，数组下标从 1 开始
    }
    int ans = t;        // 初始化总开心天数为第一次获奖后的开心天数 t
    for(int i = 1; i < n; i++)  // 遍历除最后一次获奖外的所有获奖日期
    {   
        // 比较相邻两次获奖日期的间隔和 t 的大小，取较小值累加到总开心天数中
        ans += min(t, a[i+1] - a[i]); 
    }
    cout << ans;        // 输出津津累计开心的总天数
    return 0;           
}

B4006 [GESP202406 四级] 宝箱

题目需要求小杨在最大价值与最小价值差值不超过 k 的情况下，能够带走宝箱的最大总价值。 首先，读取所有宝箱的价值，并将这些价值存储在一个数组中。为了方便后续处理，会对这个数组按价值从小到大进行排序，这样能确保在后续查找区间时，区间内的最大和最小价值可以直接由区间两端确定。 接着，为了快速计算任意区间内宝箱的总价值，会计算数组的前缀和。 之后，再使用双重循环来枚举所有可能的宝箱区间。外层循环遍历区间的起始位置，内层循环遍历区间的结束位置。对于每一个枚举到的区间，会检查该区间内最大价值（区间最后一个元素）与最小价值（区间第一个元素）的差值是否不超过 k。如果满足这个条件，就利用前缀和计算该区间内所有宝箱的总价值。 在遍历所有满足条件的区间过程中，会不断更新最大总价值。最终，遍历结束后得到的最大总价值就是问题的答案。

#include<bits/stdc++.h>  
using namespace std;    
int a[1010101];         // 定义数组 a，用于存储每个宝箱的价值
int sum[1010101];       // 定义前缀和数组 sum，sum[i] 表示前 i 个宝箱价值的总和

int main()
{   
    int n, t;           // 定义两个整型变量，n 表示宝箱数量，t 表示价值差限制 k
    cin >> n >> t;      // 从标准输入读取 n 和 t 的值
    for(int i = 1; i <= n; i++)  // 循环读取 n 个宝箱的价值
    {   
        cin >> a[i];    // 将每个宝箱的价值存储到数组 a 中，数组下标从 1 开始
    }
    sort(a + 1, a + n + 1);  // 对宝箱价值数组进行排序，使数组有序
    for(int i = 1; i <= n; i++)  // 计算前缀和数组
    {   
        sum[i] = sum[i - 1] + a[i];  // 当前位置的前缀和等于前一个位置的前缀和加上当前宝箱的价值
    }
    int ans = 0;        // 初始化最大总价值为 0
    for(int i = 1; i <= n; i++)  // 枚举区间的左端点 i
    {   
        for(int j = i; j <= n; j++)  // 枚举区间的右端点 j
        {   
            if(a[j] - a[i] <= t)  // 判断该区间内最大价值和最小价值的差是否满足条件
            {   
                int res = sum[j] - sum[i - 1];  // 利用前缀和计算该区间内宝箱的总价值
                ans = max(ans, res);  // 更新最大总价值
            }
        }
    }
    cout << ans;        // 输出最大总价值
    return 0;          
}