[C++知识库]（C++）vector的upper_bound函数和back函数

前言：

在做力扣时，在 “ 1894. 找到需要补充粉笔的学生编号 ” 的解答中，官方解答的法二 “ 前缀和 + 二分查找 ” 遇到了这两个函数，顺道总结记录下。1894题目和解法放在最后（附官方链接）

一、upper_bound函数

upper_bound(left, right, k, cmp);   //cmp函数的书写

bool cmp(const int &x, const int &y){

return x > y;

}

upper_bound函数：

对一个有序序列的一个左闭右开的有序区间进行二分查找，区间左端点和右端点分别为第1、2个参数，第三个参数是查找的值，第四个参数可填一个cmp函数，也可不填。

返回容器中第一个大于目标值的位置。若容器中的元素都比目标值小则返回最后一个元素的下一个位置。

参考：

函数学习-upper_bound与lower_bound函数 - 七铭的魔法师 - 博客园 (cnblogs.com)

谈谈自己对STL中lower_bound()函数和upper_bound()函数的理解_ryanxw growing-CSDN博客

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

int main() {
	vector<int> example{3, 5, 11, 20, 25, 31, 38, 55};
	
    vector<int>::iterator lower, upper;
    lower = lower_bound(example.begin(), example.end(), 11);  //返回的是第一个不小于给定元素key的位置
    upper = upper_bound(example.begin(), example.end(), 20);  //返回的是第一个大于给定元素key的位置
    cout << "first >= 11 is " << (lower - example.begin()) << endl;  //example[2] = 11
    cout << "first up 20 is " << (upper - example.begin()) << endl;  //example[4] = 25
    
    return 0;
}

二、back函数

遍历函数：

reference back(): 返回尾元素的引用

“ back 得到数组的最后一个单元的引用 ”

int main(){
    vector<int> example{1, 2, 3, 4};
    cout << "The last element is: " << example.back() << endl;
    return 0;
}

// 输出：4

#include <iostream>
#include<vector>
using namespace std;

int main() {
	// your code goes here
	vector<int> example{1, 2, 3, 4};
    example.at(example.size() - 1) = 5;
    cout << "The last element is: " << example.back() << endl;
    for(auto it = example.begin(); it != example.end(); it++){
    	cout << *it << endl;
    }
	return 0;
}

// 输出：5

?

三、1894题目和解法

1894. 找到需要补充粉笔的学生编号

一个班级里有?n?个学生，编号为 0?到 n - 1?。每个学生会依次回答问题，编号为 0?的学生先回答，然后是编号为 1?的学生，以此类推，直到编号为 n - 1?的学生，然后老师会重复这个过程，重新从编号为 0?的学生开始回答问题。

给你一个长度为 n?且下标从 0?开始的整数数组?chalk?和一个整数?k?。一开始粉笔盒里总共有?k?支粉笔。当编号为?i?的学生回答问题时，他会消耗 chalk[i]?支粉笔。如果剩余粉笔数量 严格小于?chalk[i]?，那么学生 i?需要 补充?粉笔。

请你返回需要 补充?粉笔的学生 编号?。

示例 1：

输入：chalk = [5,1,5], k = 22
输出：0
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。
- 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。
编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。
示例 2：

输入：chalk = [3,4,1,2], k = 25
输出：1
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 3 支粉笔，然后 k = 22 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 18 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 17 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 15 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 12 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 8 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 7 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 5 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 2 。
编号为 1 的学生没有足够的粉笔，所以他需要补充粉笔。
?

提示：

chalk.length == n
1 <= n <= 10^5
1 <= chalk[i] <= 10^5
1 <= k <= 10^9

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        int n = chalk.size();
        if (chalk[0] > k) {
            return 0;
        }
        for (int i = 1; i < n; ++i) {
            chalk[i] += chalk[i - 1];
            if (chalk[i] > k) {
                return i;
            }
        }

        k %= chalk.back();

        // 返回数组中第一个大于被查数的值
        return upper_bound(chalk.begin(), chalk.end(), k) - chalk.begin();
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-the-student-that-will-replace-the-chalk/solution/zhao-dao-xu-yao-bu-chong-fen-bi-de-xue-s-qrn1/
来源：力扣（LeetCode）