【BZOJ1029】建筑抢修(贪心)
贪心 建筑
2023-09-11 14:14:41 时间
【BZOJ1029】建筑抢修(贪心)
题面
题解
感觉自己已经不会贪心了。
很明显的一个想法是按照终止时间排序,然后能选则选。
但是这样子可能会因为前面选择了一个修理时间很长的,导致现在这个不能选。
那么我们加一个大根堆,把所有已经选择的修理时间全部压进去。
如果当前这个不能选的话,检查是否能够减少修堆顶那个,来让现在这个能够被修。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define ll int
#define pi pair<ll,ll>
#define mp make_pair
#define fr first
#define sd second
inline ll read()
{
ll x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
pi p[150100];
priority_queue<ll> Q;
int main()
{
int n=read();
for(int i=1;i<=n;++i)p[i].sd=read(),p[i].fr=read();
sort(&p[1],&p[n+1]);
ll nw=0;int ans=0;
for(int i=1;i<=n;++i)
{
if(nw+p[i].sd<=p[i].fr)
++ans,Q.push(p[i].sd),nw+=p[i].sd;
else
{
ll u=Q.top();
if(u>p[i].sd)
Q.pop(),Q.push(p[i].sd),nw-=u-p[i].sd;
}
}
printf("%d\n",ans);
return 0;
}
相关文章
- 野生前端的数据结构练习(12)贪心算法
- LeetCode-1710. 卡车上的最大单元数【自定义排序,贪心】
- 传感器|基于改进贪心算法的最佳传感器位置选择(Matlab代码实现)
- 野生前端的数据结构练习(12)贪心算法
- 【bzoj3105】【cqoi2013】【新Nim游戏】【线性基+贪心】
- 1546. 和为目标值且不重叠的非空子数组的最大数目-贪心算法
- 670. 最大交换-动态规划+贪心算法-力扣最快算法
- .删除子字符串的最大得分-c语言贪心算法
- HDU 3697 Selecting courses(贪心)
- HDU2037 今年暑假不AC 【贪心】
- 贪心算法——状态不重复,无法使用dp优化的时候就要考虑了
- 数据结构和算法 二十一、贪心算法
- 【C++】算法集锦(14):贪心算法