A27381. 滑雪板打包问题
填空题
较易
知识点
题目描述
滑雪板打包问题
题目描述
一家新开业的滑雪场，需要采购不同规格的滑雪板，每个滑雪板的长度是不固定 的，现在需要把排列好的滑雪板用木板做成木箱封装好进行快递，每次快递的总重 量是有限制的，不能超过重量 G。只要每次打包的重量不超过 G，多个滑雪板可以摞 放在一起，使用与最长滑雪板长度相同的两个木板进行固定。假设，给出排列好的 每个滑雪板的重量 Gi ，和长度 Li ，请计算需要最少多长的木板才能将所有的滑雪板 把包好。
输入格式
输入的第一行有两个数字，一个是滑雪板的个数，一个是包裹总重量。 以下滑雪板个数行，每行的第一个数是滑雪板的重量Gi 和长度 Li。
输出格式
输出需要最少的木板的总长度。注：每次打包需要 2 个木板。
样例输入(测试数据不包含本样例)
5 5
2 1
1 2
1 3
2 3
2 2样例输出
10参考答案
#include <iostream >
#include <vector>
#include <algorithm >
using namespace std;
int main() {
int n, G;
cin > > n > > G;
vector<pair<int, int> > skis(n);
for (int i = 0; i < n; i ++) {
cin > > skis [i].first > > skis [i].second;
}
int total_length = 0;
int current_weight = 0;
int max_len = 0;
for (int i = 0; i < n; i ++) {
if (current_weight + skis [i].first < = G) {
current_weight + = skis [i].first;
max_len = max(max_len, skis [i].second);
} else {
total_length + = 2 * max_len;
current_weight = skis [i].first;
max_len = skis [i].second;
}
}
// 处理最后一组
total_length + = 2 * max_len; 32
cout < < total length < < endl;答案解析
问题分析 ：将滑雪板分组打包 ，每组的总重量不超过 G ，每组需要两块木板 ，长度为该组中最长滑雪板的长度。 目标是求所有木板的最小总长度。
关键步骤 ：
● 贪心算法 ：尽量将滑雪板按顺序分组 ，使得每组的总重量不超过 G ，同时记录每组的最长长度。
● 每组需要两块木板 ，总长度为所有组长度的两倍之和。
边界条件 ：滑雪板的顺序不能改变 ，必须按输入顺序分组。
上一题
下一题