独木舟(贪心)

落日映苍穹つ 2022-05-15 02:35 143阅读 0赞

## 独木舟(贪心) ##

魔法学院放暑假了，WC和他的一帮魔友一起去弗尔夫斯基山脉玩。莫伊拉同学突然想划船到对岸找被削的Mercy玩，这里的每一艘船都是同一型号，能承受的重量都是一样的，并且每艘船都可以坐一个或者两个人。WC他们共有n个人，现在我们知道他们每个人的质量，而且每个人体重也不超过船的承重。可惜经费有限，他们必须租尽可能少的船，请问他们最少要租几艘船？  
Input  
第一行包含两个正整数n 和m ，n<=10^4,m<=2\*10^9，表示人的数量和船的最大承重。 接下来n行，每行一个正整数，表示每个人的体重。体重不超过m。  
Output  
一行一个整数表示最少需要的独木舟数。  
Sample Input  
3 6  
1  
2  
3  
Sample Output  
2  
分析：

简单贪心问题，先sort升序排序，安排最轻的和最重的在一起

代码总览：

//独木舟
    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    int a[100000],visit[100000];
    int main()
    {
        int n,m,i,j;
        while(scanf("%d %d",&n,&m)!=EOF)
        {
            int count=0;
            for(i=0;i<n;i++)
            {
       scanf("%d",&a[i]);
             visit[i]=0;
            }
            sort(a,a+n);
            for(i=0;i<n;i++)
              {
              for(j=n-1;j>=0;j--)
                {
                    if(visit[i]==0&&visit[j]==0&&a[i]+a[j]<=m)
                    {
                     visit[i]=visit[j]=1;
                     count++;
                     break;
                    }
                }
              }
              for(i=0;i<n;i++)
              if(visit[i]==0)
              count++;
              printf("%d\n",count); 
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 1848: 独木舟上的旅行

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

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

相关 51Nod 1432 独木舟

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

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

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

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

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

相关 NYOJ 71 独木舟上的旅行

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

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

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

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

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

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

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

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

相关独木舟上的旅行

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

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

相关独木舟上的旅行2

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

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

相关独木舟

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

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

相关独木舟(贪心)

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

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