UVa 1149 Bin Packing 【贪心】

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 #define mod=1e9+7;
12 using namespace std;
13 
14 typedef long long LL;
15 const int maxn=100005;
16 int a[maxn];
17 
18 int main()
19 
20 {
21 
22     int ncase,i,j,w,n,sum;
23     cin>>ncase;
24     int t=0;
25     while(ncase--)
26     {
27         t++;
28         sum=0;
29         memset(a,0,sizeof(a));
30         cin>>n>>w;
31         for(i=1;i<=n;i++) cin>>a[i];
32         
33         sort(a+1,a+n+1);
34         i=1;
35         j=n;
36         while(i<=j)
37         {
38             if(a[i]+a[j]<=w&&i!=j)
39             {
40                 i++;
41                 j--;
42                 sum++;
43             }
44             else
45             {
46                 j--;
47                 sum++;
48             }
49         }
50         if(t!=1) printf("\n");
51         printf("%d\n",sum);        
52     }
53     return 0;
54 }