题意:n个房子要修理,每个房子有修理时间和限制时间,如果在限制时间内房子没有修理好就报废了,问最多修理好几个房子。
我们贪心的先修限制时间小的,并用一个大根堆存修理时间,如果遇到一个房子修理不了,尝试和之前修理过的房子中修理时间最长的换,这样可以减少总时长,并且也合法,因为换了之后,被影响的那几个房子的开始修理时间会提前。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<std::pair<i64, i64> > a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i].first >> a[i].second;
}
std::sort(a.begin(), a.end(), [&](std::pair<i64, i64> & a, std::pair<i64, i64> & b) {
return a.second < b.second;
});
std::priority_queue<i64> heap;
i64 t = 0;
for (int i = 0; i < n; ++ i) {
if (t + a[i].first > a[i].second) {
if (heap.top() > a[i].first && t - heap.top() + a[i].first <= a[i].second) {
t -= heap.top();
t += a[i].first;
heap.pop();
heap.push(a[i].first);
}
} else {
t += a[i].first;
heap.push(a[i].first);
}
}
std::cout << heap.size() << "\n";
}