描述
进行一次独木舟的旅行活动,独木舟可以在港口租到,并且之间没有区别。一条独木舟最多只能乘坐两个人,且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销,所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序,读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则,计算要安置所有旅客必须的最少的独木舟条数,并输出结果。
输入
第一行输入s,表示测试数据的组数;
每组数据的第一行包括两个整数w,n,80<=w<=200,1<=n<=300,w为一条独木舟的最大承载量,n为人数;
接下来的一组数据为每个人的重量(不能大于船的承载量);
输出
每组人数所需要的最少独木舟的条数。
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 301;
int num[maxn];
bool judge[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int w ,n,last,j,flag=1;
scanf("%d %d",&w,&n);
memset(judge,1,n);
for(int i=0;i<n;++i)
{
scanf("%d",&num[i]);
}
sort(num,num+n);
int ans=0;
for(int i=n-1;i>0;--i) //每次给最重的一个人配一个最合适的人
{
if(judge[i]==0)
{
continue;
}
j=i-1;
while(num[i] + num[j]>w || (num[i]+num[j]<=w && judge[j]==0 ) ) //去找能和自己一起上船的并且体重最大的那个人
{
j--; //去找下一个人
if(j<0) //找不到合适的人了,只能i这个人自己走
{
//printf("这个人独自上船,他是%d\n",num[i]);
judge[i]=0;
ans++;
flag=0;
break;
}
}
if(flag) //找到合适的那个人了
{
//printf("这两个人一起上船,他是%d %d\n",num[i],num[j]);
judge[j]=0;
judge[i]=0;
ans++;
}
flag=1;
}
if(judge[0]){ //看最轻的人有没有被配对
printf("%d\n",ans+1);
}else printf("%d\n",ans);
}
return 0;
}