勵志用少的代碼做高效表達

---

題意

給定N個物品的中聯L1，背包的容量M，同時要求每個背包最多裝兩個物品，求至少要多少個背包才能裝下所有的物品。

解題過程

第一次接觸背包類問題。

最初的思路是降序排序，i從最大值遍歷，j從i后遍歷，直到找到可以裝在一個背包里的兩個物體，若無，則把最大值單獨裝包。時間復雜度為O(n^2)，超時且復雜。

網搜后，發現更優化的思路是：升序排序，從i最小的值遍歷，j從最大的值遍歷，若二者和滿足條件，則裝包， 反之將較大值單獨裝包。

于是我陷入了思考， 為什么只是將排序調整一下，時間復雜度和代碼復雜度大不相同呢？

經過腦暴，我得到了以下結論：
如果降序排序，每遍歷一次，不符合條件者會被跳過，進而參與一次又一次的循環判斷；
而升序排序后，每遍歷一次，無論是否符合條件，都會被處理，因此效率大大提高(簡單二分的原理，分而治之)。
也正因后者每次遍歷都會做相應的處理，因此每次判斷都會控制在數列的兩端，思路就會簡單很多。

可見，一道題的AC與否往往在一念之間，如果靈活一些思考，或許會更快更好的解決問題。

下面貼代碼。

需要注意的是，雖然N<=10^5， 但數組設為a[100005]會爆掉。 最后改成了a[100010]，成功AC。也算是一個小技巧。

#include<bits/stdc++.h> using namespace std; int a[100010]; int main() {ios::sync_with_stdio(false);int T; cin>>T; while(T--) {int n, num; cin>>n>>num;for(int i = 0; i < n; i++) cin>>a[i];sort(a, a+n);int i = 0, j = n-1, sum = 0;while(i <= j) {if(i == j) { sum++; break; } if(a[i]+a[j] <= num) { i++; j--; sum++; } else { j--; sum++; }}cout << sum << endl << (T?"\n":"");} return 0; }

總結

以上是生活随笔為你收集整理的20行代码AC_ 习题8-1 Bin Packing UVA - 1149(贪心+简单二分解析)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。