akoj-1267-カヌーの揺れ


カヌーの揺れ
Time Limit:1000MS  Memory Limit:65536K Total Submit:76 Accepted:44
Description
カヌーの旅行活動を行い、カヌーは港で借りることができ、違いはありません.1隻のカヌーは最大2人しか乗れず、乗客の総重量はカヌーの最大積載量を超えてはならない.私たちは今回の活動の費用をできるだけ減らさなければならないので、すべての旅客を配置できる最低のカヌーの数を見つけなければならない.今、カヌーの最大積載量、旅客数、旅客1人当たりの重量を読み込むプログラムを書いてください.与えられたルールに基づいて、すべての旅客を配置するために必要な最小限のカヌーの数を計算し、結果を出力します.
Input
第1行はsを入力し、テストデータのグループ数を表す.各データの第1行は、2つの整数w,n,80<=w<=200,1<=n<=300を含み、wはカヌーの最大積載量であり、nは人数である.次のデータのセットは、一人一人の重量(船の荷重量より大きくはならない)です.
Output
各組の人数に必要な最低カヌーの数.
Sample Input
3
85 6
5 84 85 80 84 83
90 3
90 45 60
100 5
50 50 90 40 60

Sample Output
5
3
3

Source
#include <stdio.h>
#include <string.h>
#define MAXN 300 + 10

int a[MAXN];

void my_sort(int b[], int n)
{
	int i, j, t;
	for ( i=0; i<n-1; i++ ) {
		for ( j=i+1; j<n; j++ ) {
			if ( b[i] > b[j] ) {
				t = b[i];
				b[i]= b[j];
				b[j] = t;
			}
		}
	}
}

int main()
{
	int s, w, n, i, c, j;
	scanf("%d", &s);
	while ( s-- )
	{
		memset(a, 0, sizeof(a));
		c = 0;
		scanf("%d%d", &w, &n);
		for ( i=0; i<n; i++ ) {
			scanf("%d", &a[i]);
		}
		my_sort(a, n);
		for ( i=0, j=n-1; i<=j; ) {
			if ( a[i] + a[j] <= w ) {//           ,             ,    (1) 
				i++;
				j--;
				c++;
			}
			else if ( i == j ) {  //       ,      
				c++;
			}
			else {
				j--; //          ,            ,  (1)     
				c++;
			}
		}
		printf("%d
", c); } return 0; }