题目来源
- 华为机试:导师请吃火锅
题目描述
题目解析
贪心
#include <iostream>
#include <utility>
#include <vector>
#include <random>
#include <iterator>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <iostream>using namespace std;class Solution{
public:int eatCount(std::vector<int> &x, std::vector<int> &y, int cold){std::vector<int> arr(x.size());for (int i = 0; i < x.size(); ++i) {arr[i] = x[i] + y[i];}std::sort(arr.begin(), arr.end());int cnt = 1;int nextTime = arr[0] + cold;for (int i = 1; i < arr.size(); ++i) {if(arr[i] >= nextTime){nextTime = arr[i] + cold;cnt++;}}return cnt;}
};int main(){int n, m;std::cin >> n >> m;std::vector<int> x(n, 0);std::vector<int> y(n, 0);for (int i = 0; i < n; ++i) {std::cin >> x[i];std::cin >> y[i];}Solution a;std::cout << a.eatCount(x, y, m);return 0;
}
动态规划