【C++】力扣101-分配问题和区间问题

1.有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃一个饼干，且只有饼干的大小不小于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

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

int calculate(vector<int>& hungry, vector<int>& size);
int main(void) {
  vector<int> hungry;//孩子的饥饿度数组
  vector<int> size;//饼干的大小

  int hun = 0;
  int cook = 0;
  int chilren_num = 0;
  int cookie_num = 0;
  cout << "请输入孩子的数量：";
  cin >> chilren_num;
  cout << "请输入饼干的数量：";
  cin >> cookie_num;

  while (chilren_num > 0) {
    cout << "请输入孩子的饥饿度：";
    cin >> hun;
    hungry.push_back(hun);
    chilren_num--;
  }
  while (cookie_num > 0) {
    cout << "请输入饼干的大小：";
    cin >> cook;
    size.push_back(cook);
    cookie_num--;
  }
  int satisfied = calculate(hungry, size);
  cout << "最多能满足" << satisfied << "个孩子的饥饿度。" << endl;
  return 0;
}

int calculate(vector<int>& hungry, vector<int>& size) {
  sort(hungry.begin(), hungry.end());
  sort(size.begin(), size.end());
  int i = 0;
  int j = 0;
  while (i < hungry.size() && j < size.size()) {
    if (hungry[i] <= size[j]) {
      i++;
    }
    j++;
  }
  return i;
}

 2.一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所有孩子至少要有一个糖果。求解最少需要多少个糖果。

题解：做完了题目 455，你会不会认为存在比较关系的贪心策略一定需要排序或是选择？虽然这一道题也是运用贪心策略，但我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为 1；

先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；

再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。

通过这两次遍历，分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。

在样例中，我们初始化糖果分配为 [1,1,1]，第一次遍历更新后的结果为 [1,1,2]，第二次遍历更新后的结果为 [2,1,2]。

#include <iostream>
#include <vector>
#include <algorithm>  //使用max需要用到
#include <numeric>  //使用accumulate()函数需要用到
using namespace std;
int getMinNum(vector<int>& scores);
int main(void) {
  int chilren_num;//孩子的数量
  int grade = 0;//孩子的分数
  vector<int> scores;
  cout << "请输入孩子的数量：";
  cin >> chilren_num;
  while (chilren_num > 0) {
    cout << "请输入各个孩子的分数：";
    cin >> grade;
    scores.push_back(grade);
    chilren_num--;
  }
  cout << "最少需要" << getMinNum(scores) << "个糖果。\n";

  return 0;
}

int getMinNum(vector<int>& scores) {
  if (scores.size() < 2) {
    return 1;
  }
  vector<int> num(scores.size(), 1);
  //从左到右遍历
  for (int i = 1; i < scores.size(); ++i) {
    if (scores[i] > scores[i - 1]) {
      num[i] = num[i - 1] + 1;
    }
  }
  //从右到左遍历
  for (int j = scores.size() - 1; j > 0; --j) {
    if (scores[j] < scores[j - 1]) {
      num[j] = max(num[j], num[j] + 1);
    }
  }
  return accumulate(num.begin(), num.end(), 0);
}

3.给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。输入是一个数组，数组由多个长度固定为 2 的数组组成，表示区间的开始和结尾。输出一个整数，表示需要移除的区间数量。题解：在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。我们这里使用 C++ 的 Lambda，结合 std::sort() 函数进行自定义排序。在样例中，排序后的数组为 [[1,2], [1,3], [2,4]]。按照我们的贪心策略，首先初始化为区间[1,2]；由于 [1,3] 与 [1,2] 相交，我们跳过该区间；由于 [2,4] 与 [1,2] 不相交，我们将其保留。因

此最终保留的区间为 [[1,2], [2,4]]。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int getNum(vector<vector<int>> ves) {
  if (ves.empty()) {
    return 0;
  }
  //先给每个数组的结尾数排序
  sort(ves.begin(), ves.end(), [](vector<int>& a, vector<int>& b) {
    return a[1] < b[1];
    });
  int prev = ves[0][1];
  int num = 0;
  for (int i = 1; i < ves.size(); i++) {
    if (ves[i][0] < prev) {
      num++;
    }
    else {
      prev = ves[i][1];
    }
  }
  return num;
}
int main(void) {
  vector<vector<int>> ves = { {1,2},{2,4},{1,3} };
  cout << "有" << getNum(ves) << "个数组与其它数组重叠！" << endl;
  return 0;
}