首先对所有任务按照截止时间轴排序。然后遍历所有任务时,如果加入当前任务之后的总工作时间不超过截止时间,则可以完成他们,将该任务加入答案。否则就不得不去掉其中一个。我们去掉占用时间最大的那个即可让答案尽可能优。
const int N = 150010;
int n;
// t, p
std::pair<i64, i64> task[N];
std::priority_queue<i64> q;
int main()
{
n = rd();
for (int i = 1; i <= n; ++i)
task[i].second = rd(), task[i].first = rd();
std::sort(task + 1, task + n + 1);
i64 ans = 0, cur_sum = 0;
for (int i = 1; i <= n; ++i)
{
cur_sum += task[i].second, q.push(task[i].second);
if (cur_sum <= task[i].first) ++ans;
else cur_sum -= q.top(), q.pop();
}
wr(ans);
}