1 条题解

  • 0
    @ 2025-5-12 23:57:20

    解题思路

    1. 输入与排序:首先读取物品数量 n、箱子长度 len 以及每个物品的长度数组 a。然后对物品长度数组 a 进行排序,这样能方便后续判断物品组合是否能放入箱子。
    2. 贪心策略装箱:使用双指针法,左指针 l 指向数组开头,右指针 r 指向数组末尾。不断检查当前指针所指的两个物品长度之和与箱子长度 len 的关系:
      • 若两物品长度之和大于 len,则将长的物品单独放入一个箱子,右指针 r 左移一位,箱子数 sum 加1。
      • 若两物品长度之和不大于 len,则将这两个物品放入同一个箱子,左指针 l 右移一位,右指针 r 左移一位,箱子数 sum 加1。
    3. 处理剩余物品:循环结束后,若 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
    上传者