NYOJ - 独木舟上的旅行(贪心)
发布日期:2021-07-01 00:14:54
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月07日 10时04分38秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
ACM 2013 长沙区域赛 Collision (几何)
2019-04-30
ACM 2014 鞍山区域赛 E - Hatsune Miku (dp)
2019-04-30
反向传播&梯度下降 的直观理解程序(numpy)
2019-04-30
CodeForces - 931B World Cup (思维 模拟)
2019-04-30
ACM 2017 北京区域赛 J-Pangu and Stones(区间dp)
2019-04-30
java常用类 String面试题
2019-04-30
利用ffmpeg合并音频和视频
2019-04-30
select下拉框分组展示插件的使用--(select-mania插件的使用)
2019-04-30
Java Lambda表达式的应用--Stream API操作集合框架
2019-04-30
Myslq连接(JDBC)url属性的参数的设置
2019-04-30
关于Spring MVC与前端的交互
2019-04-30
大厂经典面试题:Redis为什么这么快?
2019-04-30
Android之Retrofit基本用法篇
2019-04-30
Netty与网络协议资料整理
2019-04-30
golang实现大数据量文件的排序
2019-04-30
golang中的time包
2019-04-30
2019NOIP D4题 加工领奖
2019-04-30