NYOJ - 独木舟上的旅行(贪心)
发布日期:2021-07-01 00:14:54
浏览次数:3
分类:技术文章
本文共 989 字,大约阅读时间需要 3 分钟。
- 内存限制:64MB 时间限制:3000ms
题目描述:
进行一次独木舟的旅行活动,独木舟可以在港口租到,并且之间没有区别。一条独木舟最多只能乘坐两个人,且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销,所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序,读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则,计算要安置所有旅客必须的最少的独木舟条数,并输出结果。
输入描述:
第一行输入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
解题思路:
按从小到大先排序,然后第一个和最后一个相加,如果结果比船的载重大,那么就把指向最后一个的指针往前移动一个,第一个不动,船数加一,然后第一个和倒数第二个相加,如果比载重小,那么指向第一个的指针往后移动一个,倒数第二个指针往前移动,船数加一,以此类推。
#include#include using namespace std;int main(){ int t, w, n, ans, arr[310]; cin >> t; while (t--) { ans = 0; cin >> w >> n; for (int i = 0; i < n; i++) cin >> arr[i]; sort(arr, arr + n); for (int i = 0, j = n - 1; i <= j; j--) { if (arr[i] + arr[j] <= w) i++; ans++; } cout << ans << endl; } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/84073199 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年05月04日 06时45分53秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
一些非常实用的 Android 开发资源 【转】
2019-05-01
基础应用框架之Image Pool
2019-05-01
FTP 协议
2019-05-01
网络编程基础知识
2019-05-01
通过java枚举实现的单例jdbc连接与关闭
2019-05-01
java中的ClassLoader类加载器
2019-05-01
java中的动态代理》》》》》
2019-05-01
实现简单Spring框架核心-------!!
2019-05-01
java5线程并发库
2019-05-01
java5线程并发库中的工具
2019-05-01
致创业者的一封信(转)
2019-05-01
Eclipse快捷键
2019-05-01
JSP / GSP 标签库-Shiro权限学习1
2019-05-01
JS中button控件click事件无法响应的问题
2019-05-01
Layui前端框架导航栏使用介绍
2019-05-01
Commons Email开源项目使用
2019-05-01
Java中Properties文件读取工具类
2019-05-01
JSP中四种传递参数的方法
2019-05-01
java 重定向和转发的区别
2019-05-01
Apache Shiro介绍
2019-05-01