A27377. 定制架子问题
填空题
较易
知识点
题目描述
定制架子问题
题目描述
李莳花要做一个架子，把她喜欢的摆件叠放起来，她的每个摆件的位置顺序是固定的。这个架子的宽度是 W，每层排放的摆件不能超过这个宽度，每层架子的高度不能低于最高的摆件的高度。假设，给出排列好的每个摆件的宽度 Wi，和高度 Hi，请计算需要最少多高的架子。
输入格式
输入的第一行有 2 个数字，一个是摆件的个数 n，和架子的宽度 W。
以下摆件个数 n 行，每行的第一个数是摆件的宽度 Wi和高度 Hi。
输出格式
输出放置摆件架子的最低高度。
样例输入
5 5
2 1
1 2
1 3
2 3
2 2样例输出
5参考答案
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n, W;
std::cin >> n >> W;
std::vector<std::pair<int, int>> pieces(n);
for (int i = 0; i < n; ++i) {
std::cin >> pieces[i].second >> pieces[i].first;
}
std::sort(pieces.begin(), pieces.end());
int maxHeight = 0;
int currentHeight = 0;
for (const auto &piece : pieces) {
if (currentHeight + piece.first <= maxHeight) {
maxHeight = std::max(maxHeight, currentHeight + piece.first);
} else {
maxHeight = std::max(maxHeight, piece.first);
currentHeight = piece.first;
}
}
std::cout << maxHeight << std::endl;
return 0;
}
上一题
下一题