UVa 1149 - Bin Packing（贪心＋二分查找）

发表于 分类于 ， Disqus：

简单的贪心问题。输入n个物品的重量，背包的容量m，每个背包最多装两个物品，问需要多少个背包。

思路很简单，最小的和最大的匹配，装不下就改找比那个小一点的。

匹配要用二分查找，遍历会超时。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int find(vector<int> a,const int x,int bott,int top){//二分查找。
    int mid;
    while(bott<top){
        if(x>=a[top]) return top;
        mid=(bott+top)/2;
        if(x==a[mid]) return mid;
        if(x<a[mid+1]&&x>a[mid])
            return mid;
        else{
            if(x<a[mid]) top=mid-1;
            else bott=mid+1;
        }
    }
    if(top==bott&&x>=a[top]) return top;
    return  -1;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        vector<int>goods;
        int n,bagmax,temp,num=0;
        cin>>n>>bagmax;
        while(n--){
            cin>>temp;
            goods.push_back(temp);
        }
        sort(goods.begin(),goods.end());
        while(1){
            num++;
            int now=goods[goods.size()-1];
            goods.erase(goods.end()-1);
            if(!goods.size()) break;
            if(now+goods[0]>bagmax) continue;
            int k=find(goods,bagmax-now,0,(int)goods.size()-1);//匹配能装下的最大的。
            if(k!=-1) goods.erase(goods.begin()+k);
            if(!goods.size()) break;
        }
        cout<<num<<endl;
        if(t) cout<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章