题解 | #[JSOI2007]建筑抢修#

和这个题挺像的：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;
}