传送门

贪心思路：先修快炸的楼

所以我们可以凭据$T2$从大到小做一遍排序，，然后从$1\cdots n$一个一个去修，如果这栋楼不能修（也就是当前时间已经赶过$T2_{i}$)，那我们就不选之前已经修的楼中的一个耗时最长的楼，从而给之后的楼留出时间。如果不选那栋耗时最长的楼，这栋也不能修的话，我们就跳过这栋楼（之前耗时最长的楼留着），去修下一栋楼。

如何快速查找之前耗时最长的楼？

这里用的是左偏树，堆和优先行列队伍也可以，对付其他的数据布局，太菜不会。

#include <cstdio> #include <iostream> #include <algorithm> #define RI register int const int N = 170001; using namespace std; template <class T> inline void read(T &x) { x = 0; T f = 1; char c = getchar(); while(c > ‘9‘ || c < ‘0‘) { if(c == ‘-‘) f = -f; c = getchar(); } while(c >= ‘0‘ && c <= ‘9‘) { x = x * 10 + c - ‘0‘; c = getchar(); } x *= f; } int ls[N], rs[N], dis[N], val[N], root; int n; struct node { int t1, t2; }a[N]; int rt[N]; inline int get(int x) { return x == rt[x] ? x : rt[x] = get(rt[x]); } inline int merge(int x, int y) { if(!x || !y) return x | y; if(val[x] < val[y]) swap(x, y); rs[x] = merge(rs[x], y); rt[rs[x]] = x; if(dis[ls[x]] < dis[rs[x]]) swap(ls[x], rs[x]); dis[x] = dis[rs[x]] + 1; return x; } inline int del(int x) { int l = ls[x], r = rs[x]; rt[l] = l, rt[r] = r; ls[x] = rs[x] = dis[x] = 0; val[x] = -1; return merge(l, r); } inline bool cmp(node a, node b) { return a.t2 < b.t2; } int sum, ans; int main() { read(n); root = n + 1; val[root] = -1; for(RI i = 1; i <= n; i++) read(a[i].t1), read(a[i].t2); sort(a + 1, a + 1 + n, cmp); for(RI i = 1; i <= n; i++) { sum += a[i].t1; ans++; val[i] = a[i].t1; root = merge(root, i); if(a[i].t2 < sum) sum -= val[root], ans--, root = del(root); } printf("%d\n", ans); return 0; }

P4053 [JSOI2007]建筑抢修