NYOJ 71 独木舟上的旅行

蔚落 2022-08-25 05:22 325阅读 0赞

## 独木舟上的旅行 ##

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

难度： 2

描述

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

输入

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

输出

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

样例输入

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

样例输出

5 3 3

思路：略。

#include <stdio.h>
    #include <stdlib.h>
    
    int comp ( const void *a, const void *b )
    {
        return * ( int * ) a - * ( int * ) b;
    }
    
    int a[301];
    
    int main()
    {
    	int m;
    	scanf("%d",&m);
    	while (m--)
    	{
    		int w, n;
    		int i,j,sum = 0;
    		scanf("%d %d",&w,&n);
    		for (i=0; i<n; i++)
    		{
    			scanf("%d",&a[i]);
    		}
    		qsort(a,n,sizeof(int),comp);
    		i = 0;
    		j = n-1;
    		while (1)
    		{
    			if (j<=i)
    			{
    				sum += n;
    				break;
    			}
    			if (a[i] + a[j] <= w)
    			{//选择最大的和最小的上船
    				i++;
    				n -= 2;//减掉两个人
    				sum++;
    			}
    			j--;
    		}
    		printf("%d\n",sum);
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 1848: 独木舟上的旅行

1848: 独木舟上的旅行时间限制: 3 Sec 内存限制: 64 MB 提交: 73 解决: 53 您该题的状态：已完成 \[[提交][Link 1]\]

曾经终败给现在/ 2024年02月18日 22:04/ 0 赞/ 35 阅读

相关 51Nod 1432 独木舟

[1432 独木舟][1432] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 10 [难度：2级算法题][2] ![star.pn

落日映苍穹つ/ 2022年09月27日 00:27/ 0 赞/ 161 阅读

相关题目71 独木舟上的旅行

![20160728105006662][] 已AC代码： include<cstdio> include<algorithm> using nam

喜欢ヅ旅行/ 2022年09月24日 08:29/ 0 赞/ 118 阅读

相关 NYOJ 71 独木舟上的旅行

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

蔚落/ 2022年08月25日 05:22/ 0 赞/ 326 阅读

相关独木舟上的旅行--nyoj题目71

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

叁歲伎倆/ 2022年08月04日 08:56/ 0 赞/ 135 阅读

相关南阳题目71-独木舟上的旅行

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

太过爱你忘了你带给我的痛/ 2022年07月26日 11:24/ 0 赞/ 120 阅读

相关独木舟上的旅行

package 贪心; import java.util.Arrays; import java.util.Scanner; /\ \ 排序，然后找搭档过河,找不到

落日映苍穹つ/ 2022年07月12日 12:21/ 0 赞/ 359 阅读

相关独木舟上的旅行2

package 贪心; import java.util.Arrays; import java.util.Scanner; public class 独木舟上的旅行2

Love The Way You Lie/ 2022年07月12日 12:16/ 0 赞/ 218 阅读

相关独木舟

n个人，已知每个人体重。独木舟承重固定，每只独木舟最多坐两个人，可以坐一个人或者两个人。显然要求总重量不超过独木舟承重，假设每个人体重也不超过独木舟承重，问最少需要几只独木舟？

￡神魔★判官ぃ/ 2022年06月12日 06:44/ 0 赞/ 146 阅读

相关独木舟(贪心)

独木舟(贪心) 魔法学院放暑假了，WC和他的一帮魔友一起去弗尔夫斯基山脉玩。莫伊拉同学突然想划船到对岸找被削的Mercy玩，这里的每一艘船都是同一型号，能承受的重量都是一

落日映苍穹つ/ 2022年05月15日 02:35/ 0 赞/ 178 阅读