和这个题挺像的:tokitsukaze and Soldier 也是贪心主思路。 具体在解释详见代码
#include<algorithm>
#include<cmath>
#include<numeric>
#include<vector>
#include<iomanip>
#include<queue>
typedef long long ll;
const double eps = 1e-4;
using namespace std;
ll n;
vector<int> sor[100005];
struct node {
ll t1, t2;
}a[150005];
bool cmp(const node& a,const node& b)
{
if (a.t2 == b.t2)
return a.t1 < b.t1;
return a.t2 < b.t2;
}
priority_queue<int> q;
int main()
{
int n = 0; cin >> n;
int s, v;
for (int i = 1; i <= n; i++)
{
cin >> a[i].t1 >> a[i].t2;
}
sort(a + 1, a + 1 + n,cmp);//按照报废时间升序,先处理报废早的,但是到后边如果他处理时间较长影响到后续建筑,则在后边应该舍弃,利用优先队列实现。
ll sum = 0, cnt = 0;
ll ans = 0;
for (int i = 1; i <= n; i++)
{
q.push(a[i].t1);
sum += a[i].t1;
cnt++;
while (sum > a[i].t2)//当时间不够处理此建筑时,贪心删除此时最耗费时间的建筑(包括它自己)。
{
sum -= q.top();
q.pop();
cnt--;
}
ans = max(ans, cnt);
}
cout << ans<<endl;
return 0;
}