链接:https://ac.nowcoder.com/acm/contest/892/A

题意:

鸡尾酒要去很多很多地方玩,于是他一次买了 n 张机票,初始鸡尾酒在第一个城市,对于任意的i(1≤i≤n)i(1≤i≤n),第 i 张机票可以从第 i 个城市飞到第 i+1 个城市。且起飞时间和降落时间分别为ai,bi。。为了在一班飞机到站后能赶上下一班飞机,鸡尾酒在买机票的时候保证对于 任意的 i 和 i+1,有ai≤bi≤ai+1≤bi+1ai≤bi≤ai+1≤bi+1
但是由于不可抗力,某些飞机会晚点。如果对于某张机票 i(1≤i≤n)i(1≤i≤n),机票的实际降落时间ci满足ci>ai+1ci>ai+1,鸡尾酒则会认为这是航班之间的一个弟弟配合。 所有飞机的起飞降落的时间点均为整数。已知所有飞机总晚点时间之和为 t,求最多会有多少组航班之间的弟弟配合。
对晚点的定义: 假如某个飞机晚点时间为 x,则它的起飞时间不变,降落时间延后 x

思路:

贪心, 取后一班航班起飞时间和上一班航班落地时间的差值,贪心排序即可。

代码:

#include <bits/stdc++.h>
using namespace std; typedef long long LL; const int MAXN = 1e5+10;
int Up[MAXN], Down[MAXN]; int main()
{
int n, t;
cin >> n >> t;
for (int i = 1;i <= n;i++)
cin >> Up[i] >> Down[i];
vector<int> time;
for (int i = 2;i <= n;i++)
time.push_back(Up[i]-Down[i-1]+1);
sort(time.begin(), time.end());
int res = 0;
for (int i = 0;i < time.size();i++)
{
if (t >= time[i])
res++, t -= time[i];
else
break;
}
cout << res << endl; return 0;
}

  

最新文章

  1. 【转】以 java 为例,总结下 appium 里的一方法的使用心得
  2. iOS 读取相册二维码,兼容ios7(使用CIDetector 和 ZXingObjC)
  3. mysql性能优化-慢查询分析、优化索引和配置
  4. awk打印出当前行的上一行
  5. jquery之empty()与remove()区别
  6. EntityFramework系列:Repository模式与单元测试
  7. Java控制语句——break和continue
  8. 【C#学习笔记】打开新进程
  9. Python之创建tuple
  10. spring boot / cloud (十五) 分布式调度中心进阶
  11. 微信公众号开发系列-获取微信OpenID
  12. LOJ #2731. 「JOISC 2016 Day 1」棋盘游戏(dp)
  13. 动态记忆网络(DMN)
  14. css固定表头,表单内容可以滑动
  15. php抽奖概率算法
  16. Kali安装虚拟机遇到的问题
  17. unet网络讲解,附代码
  18. plsql Developer 登录oracle出现 initialization error
  19. Linux运维二:CentOS6.6系统安装后的基本配置与优化
  20. JavaScript的9个陷阱

热门文章

  1. P2936(BZOJ3396) [USACO09JAN]全流Total Flow[最大流]
  2. 第十二章: 部署Django
  3. BZOJ1146:[CTSC2008]网络管理
  4. 2011年浙大:Twin Prime Conjecture
  5. 2012年浙大:Head of a Gang
  6. DTP模型之一:(XA协议之三)MySQL数据库分布式事务XA优缺点与改进方案
  7. lwip 分析一
  8. C# 中的迭代器 yield关键字 提高性能和可读性
  9. Centos7更新阿里yum源
  10. HDU - 5094 Maze(状压+bfs)