一支独木(贪心)

zz/2024/2/25 22:18:22

一支独木


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


Input
第一行包含两个正整数n (0 接下来n行,每行一个正整数,表示每个人的体重。体重不超过1000000000,并且每个人的体重不超过m。


Output
一行一个整数表示最少需要的独木舟数。


Sample Input
3 6
1
2
3


Sample Output
2


#include<stdio.h>
#include<cstdio>
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{ll n,m,i,j,k,a[100000],sum;while(~scanf("%lld%lld",&n,&m)){   sum=0;k=0;for(i=0;i<n;i++){scanf("%lld",&a[i]);}sort(a,a+n);for(i=n-1;i>=0;i--){   for(j=k;j<=i;j++){if(a[i]+a[j]<=m){   sum++;k++;break;}   else{sum++;break;}}}printf("%lld\n",sum);}return 0;
}

思路:先将人的体重存入数组中然后sort排序,排序后我们从数组两端开始访问,看最重的与最轻的能否在一条船上,如果可以,更新最小值,否则访问下一个最大值,直到访问所有数值。


http://www.ngui.cc/zz/2641763.html

相关文章

最小生成树二·Kruscal算法(**)

最小生成树二Kruscal算法 描述 随着小Hi拥有城市数目的增加&#xff0c;在之间所使用的Prim算法已经无法继续使用了——但是幸运的是&#xff0c;经过计算机的分析&#xff0c;小Hi已经筛选出了一些比较适合建造道路的路线&#xff0c;这个数量并没有特别的大。 所以问题变成…

Crazy Search (哈希算法)

Crazy Search 给定一个字符串&#xff0c;其中含有不同的字母数量为m&#xff0c;现在求这个字符串中有多少个长度为n且长的互不相同的字符子串 举个例子, n3, m4 &#xff0c;字符串 “daababac”. 长度为3的不同的子串分别是: “daa”; “aab”; “aba”; “bab”; “bac”.…

街区最短路径问题(曼哈顿距离)

街区最短路径问题 一个街区有很多住户&#xff0c;街区的街道只能为东西、南北两种方向。 住户只可以沿着街道行走。 各个街道之间的间隔相等。 用(x,y)来表示住户坐在的街区。 例如&#xff08;4,20&#xff09;&#xff0c;表示用户在东西方向第4个街道&#xff0c;南北方…

HDU 找单词

Problem Description 假设有x1个字母A&#xff0c; x2个字母B,… x26个字母Z&#xff0c;同时假设字母A的价值为1&#xff0c;字母B的价值为2,… 字母Z的价值为26。那么&#xff0c;对于给定的字母&#xff0c;可以找到多少价值<50的单词呢&#xff1f;单词的价值就是组成一…

先验概率、后验概率、极大似然估计

先验概率 先验概率&#xff08;prior probability&#xff09;是指根据以往经验和分析得到的概率。例如投硬币事件&#xff0c;我们在执行这个事件之前就已经了解其符合二项分布&#xff0c;然后直接根据二项分布分析出的概率被称作是先验概率。它往往作为"由因求果"…

Python 网页爬虫

import re #匹配的库 import requests headers {Cookie:UM_distinctid16828a999356ee-01dbffc4bd71a8-33504275-144000-16828a99936840; CNZZDATA12553571271573548009-1546867979-%7C1546921578,Host:m.网站名称.com,User-Agent:Mozilla/5.0 (Windows NT 10.0; WOW64) Apple…

将文件数据读入结构体

将文件数据读入结构体 #include <stdio.h> #include <string.h> #include <stdlib.h> struct infostu {char no[20]; //学号 char name[20]; char sex[4];int age;char major[20]; //专业班级 }; int main() {int i0,j;struct infostu student[5…

CNN——卷积、池化与误差反向传播

卷积神经网络&#xff08;CNN&#xff09; 组成&#xff1a;输入层、卷积层、激活函数、池化层、全连接层 卷积神经网络中重要概念就&#xff1a; 深度&#xff1a;深度大小就等于所用的filter的个数[卷积层]&#xff0c;也可以理解为提取的层数。 权值共享&#xff1a;给一张…

iOS H5交互 -MUI

最近公司要求以后的项目要用iOS原生框架和h5页面结合完成,发现网上这方面的资料好少(js交互的资料是挺多的&#xff0c;我的h5页面是用MUI完成的&#xff0c;这方面的资料真的好少) 把我最近的进度做个总结 去MUI官网下载SDK 点击这里查看官方文档&#xff0c;下载SDK 下图是SD…

Hibernate配置异常

Orders和OrderItem配置 错误如图&#xff1a; 找了很久&#xff0c;才发现是因为和数据库对应的字段不同。 实体类&#xff1a; orders OrderItem xxx.hbm.xml 由于数据库对应的字段不存在itemid&#xff0c;所以图片上蓝色这一段代码应不要 数据库表格&#xff1a;