1351: 独木舟上的旅行

1351: 独木舟上的旅行

时间限制: 1 Sec   内存限制: 128 MB

题目描述

进行一次独木舟的旅行活动，独木舟可以在港口租到，并且之间没有区别。一条独木舟最多只能乘坐两个人，且乘客的总重量不能超过独木舟的最大承载量。我们要尽 量减少这次活动中的花销，所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序，读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给 出的规则，计算要安置所有旅客必须的最少的独木舟条数，并输出结果。

输入

第一行输入s,表示测试数据的组数；
每组数据的第一行包括两个整数w，n，80<=w<=200,1<=n<=300，w为一条独木舟的最大承载量,n为人数；
接下来的一组数据为每个人的重量（不能大于船的承载量）；

输出

每组人数所需要的最少独木舟的条数。

样例输入 Copy

3

85 6

5 84 85 80 84 83

90 3

90 45 60

100 5

50 50 90 40 60

样例输出 Copy

5

3

3

解析：

每艘船上只能做两个人。我们考虑一些问题。

如果一个人的重量超过了w，是不是题目无解？

一艘船上是不是最好做2个人。

我们用贪心算法。

每次扫描剩下最重和最轻的人，如果两个人能挤到一艘船上，就把两个人塞进去；如果两个人不行，说明最重的人和任何人都不能上同一条船，因此最重的人只能单独一条船。这样一个个扫描过去。

#include<bits/stdc++.h>

using namespace std;

int main(){

int s;

scanf("%d",&s);

while(s--){

int w,n;

scanf("%d%d",&w,&n);

int a[305];

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

sort(a+1,a+1+n);

int i=1,j=n,ans=0;

while(i<=j){

if(i==j){ans++;break;}

if(a[i]+a[j]<=w){

ans++;j--;i++;

}

else if(a[i]*2<=w){ans++;j--;}

else{ans+=j-i+1;break;}

}

printf("%d\n",ans);

}

return 0;

}