过河问题

水深无声 2022-06-05 10:49 225阅读 0赞

## 独木舟上的旅行 ##

时间限制：3000 ms  |  内存限制：65535 KB

难度：2

描述

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

输入

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

输出

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

样例输入

3
    85 6
    5 84 85 80 84 83
    90 3
    90 45 60
    100 5
    50 50 90 40 60

样例输出

5
    3
    3

来源：

NYOJ

代码：

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    int a[350];
    int main()
    {
        int s;
        scanf("%d",&s);
        while(s--)
        {
            int i,j,n,W,t,ans=0;
            scanf("%d%d",&W,&n);
            for(i=0; i<n; i++)
                scanf("%d",&a[i]);
            sort(a,a+n);
            for(i=0,j=n-1;j>=i;)
            {
                if(a[i]+a[j]>W)//如果大于，船的数量加一
                {
                    j--;
                    ans++;
                }
                else
                {
                    i++;
                    j--;
                    ans++;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，225人围观）

还没有评论，来说两句吧...

相关阅读

相关 java农夫过河_Java简单实现农夫过河问题示例

本文实例讲述了Java简单实现农夫过河问题。分享给大家供大家参考，具体如下：一、问题描述老伯伯要带鱼、狗、猫过河到对岸.，有一条船，只能坐一个人，老伯每次只能带一样动物

绝地灬酷狼/ 2022年11月03日 14:27/ 0 赞/ 203 阅读

相关青蛙过河

青蛙过河 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 1）一条小溪尺寸不大，青蛙可以从

我就是我/ 2022年09月29日 05:22/ 0 赞/ 162 阅读

相关农夫过河问题

> 问题：有一人带着狼羊菜来到河的左岸欲乘一只小船过到右岸,每次人只能带其中一个过河,当有人在不会有事,当无人在时,就不允 > > 许狼和羊在一起,也不允许羊和菜在一起,设计

小灰灰/ 2022年09月22日 01:15/ 0 赞/ 201 阅读

相关算法-过河问题

[参考文章：http://blog.sina.com.cn/s/blog\_41482c9f0100imky.html][http_blog.sina.com.cn_s_blo

小咪咪/ 2022年08月10日 12:48/ 0 赞/ 175 阅读

相关过河问题--nyoj题目47

过河问题时间限制： 1000 ms | 内存限制：65535 KB 难度： 5 描述在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的

╰半橙微兮°/ 2022年08月04日 08:56/ 0 赞/ 152 阅读

相关青蛙过河

Problem Description 1）一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，石柱L面积只容得下一只青蛙落脚，同样右岸也有一石柱R，石柱R面积也

怼烎@/ 2022年07月13日 03:40/ 0 赞/ 194 阅读

相关过河问题

独木舟上的旅行时间限制：3000 ms | 内存限制：65535 KB 难度：2 描述进行一次独木舟的旅行活动，独木舟可以在港口租到，并且之间没有区别。一条

水深无声/ 2022年06月05日 10:49/ 0 赞/ 226 阅读

相关 python解决过河问题

只有一艘船，三个商人三个仆人过河，每一次船仅且能坐1~2个人，而且任何一边河岸上仆人比商人多的时候，仆人会杀人越货。这是一个很经典的过河问题。题解：允许状态集合

╰半夏微凉°/ 2022年05月19日 06:47/ 0 赞/ 397 阅读

相关农夫过河问题

include <stdio.h> include <stdlib.h> define MAX_LEN 30 typedef stru

r囧r小猫/ 2022年03月26日 01:50/ 0 赞/ 244 阅读

相关过河

package com.epoint.bigdata; import java.util.ArrayList; import java.uti

冷不防/ 2022年01月21日 07:47/ 0 赞/ 225 阅读