博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
NYOJ71:独木舟上的旅行(简单贪心)
阅读量:5877 次
发布时间:2019-06-19

本文共 1191 字,大约阅读时间需要 3 分钟。

独木舟上的旅行

时间限制:
3000 ms  |  内存限制:
65535 KB
难度:
2
描述

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

输入
第一行输入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 
# include
using namespace std;int main(){ int w, n, i, t, temp, icount, head, a[301]; scanf("%d",&t); while(t--) { i=head = icount = 0; scanf("%d%d",&w,&n); while(n--) { scanf("%d",&temp); if(temp==w) ++icount; else a[i++] = temp; } sort(a, a+i); --i; while(i>=head) { if(a[i]+a[head]<=w) { ++icount; ++head; } else ++icount; --i; } printf("%d\n",icount); } return 0;}

转载于:https://www.cnblogs.com/junior19/p/6730104.html

你可能感兴趣的文章
4.2. PHP crypt()
查看>>
commandLink/commandButton/ajax backing bean action/listener method not invoked (转)
查看>>
RedHat 5.6_x86_64 + ASM + RAW+ Oracle 10g RAC (二)
查看>>
就是一个表格
查看>>
找回使用Eclipse删除的文件
查看>>
《系统架构师》——操作系统和硬件基础
查看>>
如何看待一本图书
查看>>
Linux 中如何通过命令行访问 Dropbox
查看>>
开发进度——4
查看>>
JS里验证信息
查看>>
Akka actor tell, ask 函数的实现
查看>>
windows10 chrome 调试 ios safari 方法
查看>>
Netty 4.1.35.Final 发布,经典开源 Java 网络服务框架
查看>>
详解Microsoft.AspNetCore.CookiePolicy
查看>>
SCDPM2012 R2实战一:基于SQL 2008 R2集群的SCDPM2012 R2的安装
查看>>
SQL SERVER中字段类型与C#数据类型的对应关系
查看>>
Linux lsof命令详解
查看>>
SVG path
查看>>
js判断checkbox是否选中
查看>>
多系统盘挂载
查看>>