P20004 炼气十万年 · 修为差距(二分解法)

一.解题思路

1.碎碎念

什么？！你问我为什么要在python训练题单里写cpp的题解，那当然是demon求着我出的啊嘻嘻

其实这道题是我发给他想让他做到主题单里的，但是随橙想呢家人们，他把这题塞他训练计划里了，没招了，不过我已经强烈要求他开放提交语言了，也就是说不仅限制py喽

当然，如果你仍然在练习py，那希望我这个题解能给你提供一些思路上的支持吧，至于语法就别想了，我的py也在及格线上挣扎

（如果看完对你有帮助记得点个赞再走呗嘻嘻嘻✨）

2.题目分析

这道题是想让我们去找出所有在数组中两数相减等于给定C的个数，也就是a-b=c的个数（其中a，b均属于数组num）

显然，这像是a+b Problem的变题，如果去遍历每一个数计算差值的话，很显然，复杂度会来到O(n^2)，

而这显然太暴力了！不妥！

那我们不妨换一种思路，a-b=c 不就等于 **a=b+c **吗，这样我们只需要遍历一次数组即可，找出每个数加c有几个数存在于数组内，这样就可以很优雅的得出答案了

接下来就是如何去统计有多少个数了，那么这里就要引入一个新的算法—— 二分查找 了

（PS：这题还有使用哈希表的更快解法O(n)，我会在同题的另一篇题解介绍）

我们知道，常规的查找方式，不论是直接使用count还是手写类似count查找，时间都会是n^2级别的，而如果使用二分的话，能将时间压缩到nlogn的级别

那么什么是二分呢？

二分就是每次将数组分成两部分，然后保留需要的那一部分，再重复此操作直到找到答案

二分查找的前提是 数组有序 🌰 给你一个数组num= [1,2,2,3] 当我们要找某个目标值（比如 2）在数组里出现了几次时，就可以用二分查找快速定位：

1.找到 第一个等于 2 的位置（比如下标 1）

2.找到 第一个大于 2 的位置（比如下标 3）

3.出现次数 = 下标3 - 下标1 = 2

在cpp98及以后的所有版本，都支持使用二分的迭代器lower_bound 和 upper_bound

不过我还是建议你去学一下手打二分，这对你学习算法的思维或许会有帮助！

3.算法实现

1.排序：对 num 进行升序排序

2.遍历每个数 b：

• 计算目标值 target = b + C
• 在排序后的数组中，用二分查找找到 target 出现的第一个位置（lower_bound）和最后一个位置的后一个（upper_bound）
• 目标值的出现次数 = upper_bound - lower_bound
• 累加到答案中

3.输出答案（注意用 long long 防止溢出）

注意：如果题目中C为正整数，那么这题就到这就结束了，但是可恶的demon明明题目写的C为正整数，测试集却给你C = 0的数据（题解发布时尚未整改），所以需要考虑C=0的情况，而如果c等于0的话，a=b+c就会变成a=b，这会错误的将b自身统计进去一次，所以需要每次都-1保证答案正确（这种情况其实就变成了找num中有几个除了自己以外相同的数了）

4.复杂度

时间：O(n log n)

空间：O(n)

二.完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,c;
    cin>>n>>c;

    vector<int> num(n);
    for(int i = 0;i<n;++i){
        cin>>num[i];
    }

    int ans = 0;
    sort(num.begin(),num.end());
    
    for(auto x:num){
        int a = x + c;
        auto l = lower_bound(num.begin(),num.end(),a);
        auto r = upper_bound(num.begin(),num.end(),a);
        if(c==0){
            ans += r-l-1;
        }else{
            ans += r-l;
        }
        
    }
    cout<<ans<<'\n';

    return 0;
}

PS：非专业题解！有任何错误记得联系我！！！