贪心经典题
先把所有建筑按照 t2 排序, 然后按顺序枚举每一个建筑: 若可以修就修, 否则就看一看修当前建筑, 不修已经修了的最耗时建筑能否节省时间
用优先队列维护即可
- #include "cstdio"#include "cctype"#include "queue"#include "algorithm"using namespace std;
- int read() {
- int c,
- x = 0;
- while (!isdigit(c = getchar()));
- while (x = x * 10 + c - 0, isdigit(c = getchar()));
- return x;
- }
- struct building {
- int t1,
- t2;
- }
- b[150000];
- bool comp(building a, building b) {
- return a.t2 < b.t2;
- }
- priority_queue < int > h;
- int main() {
- int n = read(),
- now = 0,
- ans = 0;
- for (int i = 0; i < n; i++) b[i].t1 = read(),
- b[i].t2 = read();
- sort(b, b + n, comp);
- for (int i = 0; i < n; i++) if (b[i].t2 >= b[i].t1 + now) now += b[i].t1,
- h.push(b[i].t1),
- ans++;
- else if (b[i].t1 < h.top()) now += b[i].t1 - h.top(),
- h.pop(),
- h.push(b[i].t1);
- printf("%d", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2513619.html