学步园

2011年北航ACM集训队集体出游期间准备一起划船游湖。询问租船点得知每条船最多只能载2人，且载重不能超过C。为了节省费用，需要使租船的条数尽量少，但又要保证每个人都有船坐。问最少要租多少条船。

输入

输入的第一行是一个整数，为数据的组数t（t<=10）。

每组数据第一行为两个整数n（1<=n<=1000）和C（1<=C<=10^9），分别表示集训队的人数和每条船的载重量。第二行为n个整数，分别表示每名队员的重量W_i（1<=W_i<=C)。

输出

对于每组数据，输出最少需要租船的条数。

样例输入
2
1 10
3
5 10
5 9 7 1 2
样例输出
1

3

水题

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
 int t;
 cin >> t;

 int a[ 1002 ];
 bool f[ 1002 ];

 for ( int e = 0; e < t; e++ )
 {
  int n, c;
  cin >> n >> c;

  for ( int i = 0; i < n; i++ )
  {
   cin >> a[ i ];
   f[ i ] = true;
  }
  
  int sum = 0;
  sort( a, a+n );
  
  for ( int i = n-1; i >= 0; i-- )
  {
   int j;
   if ( f[ i ] == true )
   {
    for ( j = i-1; j >= 0; j-- )
    {
     if ( f[ j ] == true && a[ i ] + a[ j ] < c )
      break;
    }
   
    if ( j == -1 )
     sum++;
    else
    {
     sum++;
     f[ j ] = false;
    }

    f[ i ] = false;
   }
  }

  cout << sum << endl;
 }

 return 0;
}