1 条题解
-
0
解题思路
- 输入与排序:首先读取物品数量
n
、箱子长度len
以及每个物品的长度数组a
。然后对物品长度数组a
进行排序,这样能方便后续判断物品组合是否能放入箱子。 - 贪心策略装箱:使用双指针法,左指针
l
指向数组开头,右指针r
指向数组末尾。不断检查当前指针所指的两个物品长度之和与箱子长度len
的关系:- 若两物品长度之和大于
len
,则将长的物品单独放入一个箱子,右指针r
左移一位,箱子数sum
加1。 - 若两物品长度之和不大于
len
,则将这两个物品放入同一个箱子,左指针l
右移一位,右指针r
左移一位,箱子数sum
加1。
- 若两物品长度之和大于
- 处理剩余物品:循环结束后,若
l > r
,说明所有物品都已装箱,直接输出箱子数sum
;若l == r
,说明还剩一个物品,需要额外一个箱子,输出sum + 1
。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define REP(i, s, n) for(int i = s; i <= n; i ++) #define REP_(i, s, n) for(int i = n; i >= s; i --) #define MAX_N 100000 + 10 using namespace std; int main(){ int n, len, a[MAX_N]; scanf("%d%d", &n, &len); REP(i, 1, n) scanf("%d", &a[i]); sort(a + 1, a + n + 1); int l = 1, r = n, sum = 0; while(l < r){ if(a[l] + a[r] > len) r --, sum ++; else l ++, r --, sum ++; } if(l > r) printf("%d\n", sum); else if(l == r) printf("%d\n", sum + 1); return 0; }
- 输入与排序:首先读取物品数量
- 1
信息
- ID
- 1783
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者