本题解是 【C++算法】排序与二分的函数使用教程 配套练习，题目编号为洛谷题目编号

练习计划概览

• 总时长: 约 4 小时

• 核心目标:

  1. 熟练掌握 sort 函数，特别是自定义比较函数的应用。

  2. 理解排序作为问题预处理步骤的重要性。

  3. 掌握标准二分查找及其变体（如二分答案）。

  4. 培养在看到题目时，能主动思考 O(nlogn) 复杂度的解法。

第一部分：排序预处理 (约 1.5 - 2 小时)

这部分旨在通过不同类型的排序问题，让您熟练掌握 sort 的各种用法，并体会排序在贪心、模拟等问题中的关键作用。

题解合集

//P1093 - 熟悉lambda形式的sort写法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct student		//定义结构体，方便写cmp函数
{
    int id;
    int ch;
    int mt;
    int en;
    int sum;
};

int main(){
    int n;
    cin >> n;
    vector<student> v(n);
    for (int i = 0; i < n; i++){
        v[i].id = i + 1;
        cin >> v[i].ch >> v[i].mt >> v[i].en;
        v[i].sum = v[i].ch + v[i].mt + v[i].en;
    }
    sort(v.begin(),v.end(),[](student a,student b){	//直接使用lambda表达式来sort
        if(a.sum!=b.sum){
            return a.sum > b.sum;
        }else if(a.ch!=b.ch){
            return a.ch > b.ch;
        }else{
            return a.id < b.id;
        }
    });
    for (int i = 0; i < 5; i++){
        cout << v[i].id << " " << v[i].sum << endl;
    }
    return 0;
}

//P1059 - 体会去重排序，这里直接使用set可以实现
#include <iostream>
#include <set>

using namespace std;

int main(){
    int n;
    cin >> n;
    set<int> s;
    for(int i = 0;i<n;i++){
        int x;
        cin >> x;
        s.insert(x);
    }
    cout << s.size() << endl;
    for(int i : s){
        cout << i << " ";
    }
    return 0;
}

//P1012 - 进一步习惯sort比较函数书写

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<string> v;
    while(n--){
        string s;
        cin >> s;
        v.push_back(s);
    }
    sort(v.begin(),v.end(),[](string a, string b){
        return a + b > b + a;			//使用字符串拼接后比大小
    });
    for(string s : v){
        cout << s;
    }
    return 0;
}

//P1223 - 进一步熟悉结构体sort

#include <iostream>
#include <vector>
#include <algorithm>   
#include <iomanip>

using namespace std;

struct waiter
{
    int id;
    int time;
};

int main(){
    int n;
    cin >>n;
    vector<waiter> v;
    for(int i=0; i<n ;i++){
        waiter w;
        w.id = i + 1;
        cin >> w.time;
        v.push_back(w);
    }
    sort(v.begin(),v.end(),[](waiter a,waiter b){
        return a.time < b.time;
    });
    long long sum = 0;
    
    for(int i=0; i<n ;i++){
        cout << v[i].id << " ";
        sum += v[i].time * (n-i-1); 		//注意等待不包括自己时间
    }
    cout << endl;
    cout << setprecision(2) << fixed << double(sum) / n << endl;		//对于输出格式的设置
    return 0;
}

上述题解不唯一，可以在提交页面查看更多的解答方法。

知识点纵览:

• 对于 P1093 和 P1012，重点在于思考和编写 cmp 函数。特别是 P1012，其比较方式 a+b > b+a (字符串拼接) 是一个非常巧妙的思想。

• 完成题目后，可以思考一下：如果不先排序，这些问题会变得多复杂？以此来加深对“排序预处理”的理解。

第二部分：经典二分查找 (约 2 - 2.5 小时)

这部分从基础的二分查找到更抽象的“二分答案”，旨在建立对数级复杂度的思维模型。许多看似需要遍历求解的问题，如果其答案具有单调性，就可以用二分法高效求解。

题解合集

//P2249 - 这个题解利用的是基于哈希的无序容器在查找上耗时O(1)

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main(){
    ios::sync_with_stdio(false);	//优化读写
    cin.tie(nullptr);

    int n,m;
    cin >> n >> m;

    unordered_map<int, int> pos_map;

    for(int i=0;i<n;i++){
        int val;
        cin >> val;
        if(pos_map.find(val) == pos_map.end()){
            pos_map[val] = i + 1; // 存储第一次出现的位置（1-indexed）
        }
    }

    for(int i=0;i<m;i++){
        int num;
        cin >> num;
        auto it = pos_map.find(num);
        if(it == pos_map.end()){
            cout << "-1";
        }else{
            cout << it->second;
        }
        if(i < m-1) cout << " ";
    }
    cout << "\n";

    return 0;
}

//还是上面那个题目，在洛谷上找的二分题解用于参考。
//这里提到的`binary_search`, `lower_bound`, `upper_bound`这三个函数，是在STL提供的包装好的二分函数，下面注释由原作者提供
#include<cstdio>
#include<algorithm>//用到lower_bound
using namespace std;
const int MAXN=1e6+10;//注意范围
int read(){//快读
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int a[MAXN];
int main(){
	int n=read(),m=read();//读入
	for(int i=1;i<=n;i++) a[i]=read();
	while(m--){
		int x=read();
		int ans=lower_bound(a+1,a+n+1,x)-a;//二分搜，注意-a
		if(x!=a[ans]) printf("-1 ");//没有，输出-1
		else printf("%d ",ans);//有，输出ans
	}
	return 0;//华丽结束
}

//P1102 - 这里我用map将重复数字缩短了，然后再通过查找判断是否存在。
//这个题使用二分是利用逐个找目标数字（定AC找B）的长度，即找lower_bound&upper_bound这两个边界中间数字的个数，题解略，我就不找了。^_^

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
typedef long long LL;

using namespace std;

int main(){
    int n;
    LL c;
    cin >> n >> c;
    vector<LL> v(n);
    for(int i=0;i<n;i++){
        cin >> v[i];
    }

    map<LL, int> count; // 统计每个数值出现的次数
    for(int i = 0; i < n; i++){
        count[v[i]]++;
    }

    LL result = 0;
    for(auto& p : count){
        LL val = p.first;
        int cnt = p.second;

        // 查找 val + c 是否存在
        if(count.find(val + c) != count.end()){
            result += (LL)cnt * count[val + c];
        }
    }

    cout << result << endl;
    return 0;
}

//P1678 - 先找到右临界，然后迭代器左移（自减）找到左临界，然乎比较两个差值绝对值大小

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <climits>
using namespace std;

int main(){
    int m,n;
    cin >> m >> n;

    vector<int> uni(m);
    for(int i=0;i<m;i++){
        cin >> uni[i];
    }
    sort(uni.begin(),uni.end());

    long long cnt = 0;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;

        // 找到第一个 >= x 的位置
        auto it = lower_bound(uni.begin(), uni.end(), x);

        int min_diff = INT_MAX;

        // 检查 >= x 的最小值
        if(it != uni.end()){
            min_diff = min(min_diff, abs(x - *it));
        }

        // 检查 < x 的最大值
        if(it != uni.begin()){
            --it;
            min_diff = min(min_diff, abs(x - *it));
        }

        cnt += min_diff;
    }
    cout << cnt << endl;
    return 0;
}

//P1873 - 在0到最高树之间进行二分，其中编写判断条件为核心内容

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 计算在高度h下能获得的木材长度
long long getWood(const vector<int>& trees, int h) {
    long long wood = 0;
    for (int tree : trees) {
        if (tree > h) {
            wood += tree - h;
        }
    }
    return wood;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> trees(n);

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

    // 二分查找的范围：0 到最高的树
    int left = 0;
    int right = *max_element(trees.begin(), trees.end());
    int result = 0;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        long long wood = getWood(trees, mid);

        if (wood >= m) {
            // 如果能获得足够的木材，尝试更高的高度
            result = mid;
            left = mid + 1;
        } else {
            // 如果木材不够，降低高度
            right = mid - 1;
        }
    }

    cout << result << endl;
    return 0;
}

练习建议:

• P2249 是练习二分查找细节的绝佳题目，请务必注意循环条件 (l <= r 或 l < r) 和边界更新 (r = mid - 1 或 r = mid) 的细微差别。

• P1873 是您思维进阶的关键。尝试理解为什么可以对“高度”进行二分？如何编写函数来判断在某个高度下，砍伐的木材是否足够？想通这一点，您就掌握了二分答案的精髓。

目标达成自查

完成以上练习后，您可以尝试回答以下问题，以检验学习效果：

1. 关于 sort:

   • 如何对一个结构体数组按多个优先级不同的关键字进行排序？

   • 如何通过重载运算符或自定义比较函数（lambda表达式）来实现 sort 的自定义排序？

2. 关于二分查找:

   • 二分查找算法的适用前提是什么？（单调性）

   • 如何在有序数组中查找第一个大于等于 x 的数？

   • 什么是“二分答案”？它解决的是哪一类问题？（求解满足条件的最小/最大值）