本文同步发于洛谷博客，您也可以在题解页面访问。

看一眼算法标签就知道了是贪心

ps:文章翻译有些错误

最后一行是包裹的容量

应该是

第二行是包裹的容量

解题思路

  • 对物品数组按体积由大往小排序

  • 用两个变量当前指针和后指针

  • 如果第一个和最后一个能装到箱子里，计数器 $+1$ ，前指针向后挪一位，后指针向前挪一位。否则只能装大的，计数器 $+1$ ，并且前指针要向后挪一位。

  • 重复循环直到前指针大于或等于后指针，输出结果。

流程图(自己做的，有点丑)

献上代码

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
cin>>n;
memset(V,0,sizeof(V));
p1=1,p2=n,cnt=0;
初始化
cin>>v;
for(int i=1;i<=n;i++){
    cin>>V[i];
}
数据输入
sort(V+1,V+n+1,greater<int>()); 排序
while(true){ 循环处理
    if(p1==p2||p1>p2){ 结束了
    	cnt++;  因为还有物品没装所以++
        cout<<cnt<<endl; 输出解
        break;
    }
    if(V[p1]+V[p2]<=v){ 装得下两个
        cnt++;
        p1++,p2--;
    }
    else{  只能装大的
        cnt++;
        p1++;
    }
}

完整代码

这里

Warning:有防抄袭手段,请勿抄袭!

谢谢！