独木舟上的旅行

发布时间:2024-11-12 05:27

独木舟上的旅行

最新推荐文章于 2024-05-23 00:30:00 发布

珍惜每分每秒 于 2017-01-29 14:52:46 发布

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

描述

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

输入 第一行输入s,表示测试数据的组数;
每组数据的第一行包括两个整数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<iostream>

#include<algorithm>

using namespace std;

int a[301],w,n;

int main()

{

int T,i,j,c=0;

cin>>T;

while (T--)

{

c=0;

cin>>w>>n;

for (i=0;i<n;i++)

cin>>a[i];

sort(a,a+n);

for (i=0,j=n-1; i<=j&&j>=0; )

{

if (i==j)

{

c++;

break;

}

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

{

i++;

j--;

c++;

}

else if (a[i]+a[j]>w&&a[j]<=w)

{

j--;

c++;

}

}

cout<<c<<endl;

}

return 0;

}



网址:独木舟上的旅行 https://www.yuejiaxmz.com/news/view/46272

相关内容

独自旅行
独自旅行攻略:热门目的地推荐与旅行全攻略
方舟生存进化什么恐龙强 十大最强恐龙排行
独自旅行时的10个好建议
大学生独自旅行必备好物清单✨
独自旅行的 13 条经验 – Hostelworld Travel Blog
一种生活方式 独立自由的旅行
史上最全青藏线旅行攻略
小长假,给自己安排一场“生态旅行”
旅行必备清单:让你的行程无忧无虑

随便看看