@Junlier
2018-08-31T22:12:35.000000Z
字数 1162
阅读 1949
贪心——后悔操作
洛谷题目传送门
这是一道经典的贪心后悔的题目
做过贪心加后悔的题目的应该一眼可以看出来
- 首先按倒塌时间T2排序,再从1枚举到n,能修就修,发现不能修就从前面找一个修的最慢的来后悔,当然,前提是这个最慢的要比现在要修的慢,不难证明这样肯定更优(节省了时间修后面的)。嗯,做完了,没了,代码实现
基本没难度- 还有,用堆来维护前面修过的最大值。
一般这类题都是堆吧......(具体情况具体讨论)
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 150050
using namespace std;
const int Inf=1e9;
int n,ans;
struct HOUSE{
int fixt,badt;
bool operator<(rg HOUSE a)
{
return badt<a.badt;
}
}ljl[N];
priority_queue<int>Q;
il int read()
{
rg int s=0,m=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int main()
{
n=read();
for(rg int i=1;i<=n;++i)
ljl[i]=(HOUSE){read(),read()};
rg int now=0;
sort(ljl+1,ljl+n+1);
for(rg int i=1;i<=n;++i)
{
if(now+ljl[i].fixt>ljl[i].badt)
{
if(!Q.empty())
if(ljl[i].fixt<Q.top())
{
now-=Q.top()-ljl[i].fixt;
Q.pop();
Q.push(ljl[i].fixt);
}
}
else
{
now+=ljl[i].fixt;
Q.push(ljl[i].fixt);
}
}
while(!Q.empty())ans++,Q.pop();
printf("%d\n",ans);
return 0;
}