AcWing 2356. 建筑抢修
原题链接
困难
作者:
偷月亮的喵
,
2024-11-02 16:47:05
,
所有人可见
,
阅读 2
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n;
struct node {
int a, b;
bool operator<(node& c) {
return b < c.b;
}
}a[150005];
priority_queue<int> q;
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].a >> a[i].b;
}
sort(a + 1, a + n + 1);
long long sum = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
sum += a[i].a;
q.push(a[i].a);
if (sum <= a[i].b) {
ans++;
}
else {
sum -= q.top();
q.pop();
}
}
cout << ans;
}