UVa1149 - Bin Packing

  

   

    

     

    
    

     

      //UVa1149 - Bin Packing
     
    
   

    

     

    
    

     

      //贪心，背包，乘船问题
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      int a[101000];	//bag
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
	//freopen("UVa1149.in","r",stdin);
     
    
   

    

     

    
    

     
	int t,n,m;
     
    
   

    

     

    
    

     

      	cin>>t;
     
    
   

    

     

    
    

     
	while(t--){
     
    
   

    

     

    
    

     

      		cin>>n>>m;
     
    
   

    

     

    
    

     
		for(int i=0;i<n;i++) cin>>a[i];
     
    
   

    

     

    
    

     
		sort(a,a+n);
     
    
   

    

     

    
    

     
		int left=0, right=n-1, ans = 0;
     
    
   

    

     

    
    

     
		while(left <= right){
     
    
   

    

     

    
    

     
			if(a[right]+a[left] > m) --right;
     
    
   

    

     

    
    

     
			else --right, ++left;
     
    
   

    

     

    
    

     

      			++ans;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		cout<<ans<<"\n";
     
    
   

    

     

    
    

     
		if(t)cout<<"\n";
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      //已AC
     
    
  
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/68957288