题意:问能选取最大多少个数的建筑, 满足在规定时间内,每个建筑的建立都不能超过截止时间。
解题思路:先按照截止日期排序,如果能在截止日期内完成,那么我们就尽量往里扔,如果不能完成,那么我们选择大根堆中最大的看看它是不是比当前任务耗时大,如果耗时大,那么我们一定能把它抛下,并且完成任务,并且总耗时最少。
代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=150010;
int n,m;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pii;
priority_queue<int>q;
int a[N];
int b[N];
pii qq[N];
bool cmp(pii a,pii b)
{
if(a.second!=b.second)
return a.second<b.second;
return a.first < b.first;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin >> qq[i].first >> qq[i].second;
sort(qq,qq+n,cmp);
ll t =0;
int res=0;
for(int i=0;i<n;i++)
{
if(t+qq[i].first <=qq[i].second)
{
q.push(qq[i].first);
t += qq[i].first;
res++;
}
else
{
if(q.size())
{
if(qq[i].first < q.top())
{
ll tt=q.top();
q.pop();
q.push(qq[i].first);
t = t + qq[i].first - tt;
}
}
}
}
cout << res << endl;
return 0;
}