【解题思路】

  贪心,先按结束时间排序,从左到右扫描过去,如果当前建筑可以修复则入大根堆,否则,若其修复时间比堆顶小则弹出堆顶并入堆,处理完堆后则更新总时间。复杂度O(nlog2n)。

【参考代码】

 #pragma GCC optimize(2)
#include <algorithm>
#include <cstdio>
#include <functional>
#include <set>
#define REP(i,low,high) for(register int i=(low);i<=(high);i++)
using namespace std;
struct node
{
int ft,et;
node() {}
int input() {return scanf("%d%d",&ft,&et);}
bool operator<(const node &another)const{return et<another.et;}
}a[];
int n;
multiset<int, greater<int> > sav;
int main()
{
scanf("%d",&n),sav.clear(); REP(i,,n) a[i].input(); sort(a+,a+n+);
int ans=,now=;
REP(i,,n)
{
if(a[i].ft+now<=a[i].et) sav.insert(a[i].ft),ans++,now+=a[i].ft;
else
{
multiset<int>::iterator tp=sav.begin();
if(*tp>a[i].ft) now+=a[i].ft-*tp,sav.erase(tp),sav.insert(a[i].ft);
}
}
return printf("%d\n",ans),;
}

最新文章

  1. VirtualBox Ubuntu Server 16.04 手动设置 网络(IP, DNS, 路由)
  2. fancybox 基础 简单demo
  3. [原]poj-1611-The Suspects(水并查集)
  4. [原创]Devexpress XtraReports 系列 7 创建Drill-Down(向下钻取)报表
  5. 深入浅出分析C#接口的作用
  6. php 之 数据访问 增删改查
  7. cf492A Vanya and Cubes
  8. CentOS安装配置ganglia
  9. java代码中获取进程process id(转)
  10. 如何获取view的大小
  11. Kafka 简要使用说明
  12. ELK 环境搭建1-Elasticsearch
  13. 通过灰度线性映射增强图像对比度实现PS中的色阶
  14. 杂谈迁移tomcat项目到docker,以及遇到的问题
  15. Template模板
  16. 图像YUV格式介绍
  17. 函数和常用模块【day04】:高阶函数(七)
  18. (转-经典-数据段)C++回顾之static用法总结、对象的存储,作用域与生存期
  19. 第十一章&#160;串 (c2)KMP算法:查询表
  20. 二叉树的深度优先遍历与广度优先遍历 [ C++ 实现 ]

热门文章

  1. 微信小程序 滚动到底部
  2. rstrip
  3. Github pages博客搭建与域名绑定
  4. C之输入输出函数(3) -- 请使用sscanf()
  5. js-原生js触发器使用
  6. mac 安装brew mac安装expect mac一键登录服务器脚本
  7. 1、什么是cookie?
  8. LeetCode 分隔链表
  9. 剑指offer——65和为S的连续正数序列
  10. JDK8新特性之方法引用