Datahub
数据改变生活

1351: 独木舟上的旅行

发表时间:2022-10-28 23:23

1351: 独木舟上的旅行

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

题目描述

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

输入

第一行输入s,表示测试数据的组数;
每组数据的第一行包括两个整数wn80<=w<=200,1<=n<=300w为一条独木舟的最大承载量,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;

}


文章分类: 算法例题
分享到:
QQ:258506508                                     联系电话:020-000000    000-000000                                   联系邮箱:xxx@.co.m                                     联系地址:XXX省XXX市XXX县XXX路