NYOJ 71カヌーでの旅

カヌーの旅
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
2
説明
カヌーの旅行活動を行い、カヌーは港で借りることができ、違いはありません.1隻のカヌーは最大2人しか乗れず、乗客の総重量はカヌーの最大積載量を超えてはならない.私たちは今回の活動の費用をできるだけ減らさなければならないので、すべての旅客を配置できる最低のカヌーの数を見つけなければならない.今、カヌーの最大積載量、旅客数、旅客1人当たりの重量を読み込むプログラムを書いてください.与えられたルールに基づいて、すべての旅客を配置するために必要な最小限のカヌーの数を計算し、結果を出力します.
入力
第1行はsを入力し、テストデータのグループ数を表す.
各データの第1行は、2つの整数w,n,80<=w<=200,1<=n<=300を含み、wはカヌーの最大積載量であり、nは人数である.
次のデータのセットは、一人一人の重量(船の荷重量より大きくはならない)です.
しゅつりょく
各組の人数に必要な最低カヌーの数.
サンプル入力

385 65 84 85 80 84 8390 390 45 60100 550 50 90 40 60

サンプル出力

533

/*問題解:
人の重さを小さいものから大きいものに並べ替える.一番小さいのと一番大きいのをカヌーに乗せて、だめなら次と大きい.
すべてがだめなら、単独でカヌーに乗る.残りの人は順番にこのような比較を行います. 
*/

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int s,w,n,i,j,t,judge[302],a[302];
	scanf("%d",&s);
	while(s--)
	{
		memset(judge,0,sizeof(judge));
		scanf("%d %d",&w,&n);
		for(i=0; i<n; i++)
		{
			scanf("%d",&a[i]);
		}
		sort(a,a+n);
		for(i=0,t=0; i<n; i++)
		{
			if(!judge[i])
			{ 
				for(j=n-1; j>i; j--)
				{
					if(a[i]+a[j]<=w&&!judge[j])
					{
						judge[j] = 1;
						t++;	
						break;
					}
				}
				if(judge[j]==0)  //       
						t++;
			judge[i] = 1;
			}
		}
		printf("%d
",t);
	}
}