牛客网 — [牛客小白月赛15]斑羚飞渡(贪心)
发布日期:2021-07-01 00:18:52
浏览次数:3
分类:技术文章
本文共 1317 字,大约阅读时间需要 4 分钟。
题目链接:
时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 131072K,其他语言262144K 64bit IO Format: %lld题目背景
两个人之间只能有一个活着 ,这必然是我和你的战争——Harry Potter
题目描述
水宝宝在看完《斑羚飞渡》这本书后,突发奇想,想到了一个有趣的问题
现在峡谷的这边有n只斑羚,每只斑羚跳跃的最远距离为x[i],斑羚在别人的背上起跳的最远距离为y[i],峡谷的两岸的距离为s,问在最好情况下,有几只斑羚可以用别人的背当跳板跳到对岸,但由于斑羚的先天原因(主要是太肥),只能把别人当跳板一次
注:本系列题不按难度排序哦
输入描述
第一行n,s 接下来n行,每行2个整数代表x[i],y[i]
输出描述
一行一个整数,表示有几只斑羚可以用别人的背当跳板跳到对岸
输入
5 10
6 8 2 100 7 3 1 10 2 5
输出
2
说明
第一组是第三只斑羚跳6的距离,第一只斑羚跳6的距离后从第三只的背上起跳,再跳8的距离后到达对岸
第二组是第五只跳2的距离,第二只跳2的距离后从第五只的背上起跳,跳100的距离到达对岸(假设对岸无限长,不可能跳出对岸)
备注
对于100%的数据,n<=1000000;
对于所有数据,s<=1000000000; x[i],y[i]<=s; 不保证x[i]<y[i]
解题思路
如果自己就可以跳过去,就自己跳,否则,踩背上可能跳过去就存下来,如果一定不能到,当跳板。然后就排序、配对。如果跳板不够用,就舍弃一半当跳板。
Accepted Code:
#includeusing namespace std;int sa[1000005], sb[1000005];bool cmp(int a, int b) { return a > b;}int main() { int n, s, x, y, ans, cnta, cntb; ans = cnta = cntb = 0; scanf("%d%d", &n, &s); for (int i = 0; i < n; i++) { scanf("%d%d", &x, &y); if (x >= s) ans++; else if (x + y >= s) sa[cnta++] = y; else sb[cntb++] = x; } sort(sb, sb + cntb); sort(sa, sa + cnta, cmp); int i = 0, j = 0; while (i < cnta && j < cntb) { if (sa[i] + sb[j] >= s) i++, j++, ans++; else j++; } printf("%d\n", ans + (cnta - i) / 2); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/92096251 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年05月02日 09时50分15秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
[12] JMeter-结果分析之图形图表
2021-07-04
[13] JMeter-详解JMeter参数化之CSV Data Set Config
2021-07-04
[14] JMeter关联-详解JMeter正则表达式提取器
2021-07-04
优化jmeter脚本
2021-07-04
Gradle基础使用总结1
2021-07-04
性能测试场景设置---不同场景下对应的jmeter脚本【不定时补充】
2021-07-04
登录oracle数据库时常用的操作命令整理
2021-07-04
微信小程序实现安卓机下拉不刷新,ios下拉刷新操作(自定义底部tab栏在安卓机下拉)
2021-07-04
小程序动态获取组件高度(自定义Tabbar的高度)
2021-07-04
如何是实现微信会员开卡组件中一个手机号绑定一个微信号(思路篇)
2021-07-04
has been blocked by CORS policy: Response to preflight request doesn‘t pass access control check 报错
2021-07-04
使用aspose.words 18.6实现pdf文档转换
2021-07-04
包机制介绍
2021-07-04
Java数组详解
2021-07-04
Java面向对象详解
2021-07-04
在Debian 8上使用Apt-Get安装Java
2021-07-04
vs中动态DLL与静态LIB工程中加入版本信息的方法
2021-07-04
大数据分析技术与应用一站式学习(值得收藏)_v20200418
2021-07-04