bzoj1029题解
2024-10-07 20:05:09
【解题思路】
贪心,先按结束时间排序,从左到右扫描过去,如果当前建筑可以修复则入大根堆,否则,若其修复时间比堆顶小则弹出堆顶并入堆,处理完堆后则更新总时间。复杂度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),;
}
最新文章
- VirtualBox Ubuntu Server 16.04 手动设置 网络(IP, DNS, 路由)
- fancybox 基础 简单demo
- [原]poj-1611-The Suspects(水并查集)
- [原创]Devexpress XtraReports 系列 7 创建Drill-Down(向下钻取)报表
- 深入浅出分析C#接口的作用
- php 之 数据访问 增删改查
- cf492A Vanya and Cubes
- CentOS安装配置ganglia
- java代码中获取进程process id(转)
- 如何获取view的大小
- Kafka 简要使用说明
- ELK 环境搭建1-Elasticsearch
- 通过灰度线性映射增强图像对比度实现PS中的色阶
- 杂谈迁移tomcat项目到docker,以及遇到的问题
- Template模板
- 图像YUV格式介绍
- 函数和常用模块【day04】:高阶函数(七)
- (转-经典-数据段)C++回顾之static用法总结、对象的存储,作用域与生存期
- 第十一章&#160;串 (c2)KMP算法:查询表
- 二叉树的深度优先遍历与广度优先遍历 [ C++ 实现 ]