bzoj1029: [JSOI2007]建筑抢修

按照t2从小到大排列之后贪心

若当前任务可以插入，则插入

若当前任务不可以插入，分两种情况：

任务的耗时大于等于之前插入的任务的最大耗时，跳过当前任务

任务的耗时小于之前插入的任务的耗时，将最前插入的耗时最大的那个任务删除，插入当前任务

const int N = 150010;
struct Node {
    int L, T;
    inline bool operator <(const Node &p)const {
        return L < p.L;
    }
} Dat[N];
priority_queue<int> Q;
int n;

inline void Input() {
	scanf("%d", &n);
	Rep(i, n) scanf("%d%d", &Dat[i].T, &Dat[i].L);
}

inline void Solve() {
	sort(Dat, Dat + n);
	static int total = 0, Ans = 0;
    Rep(i, n)
        if(Dat[i].T + total <= Dat[i].L) Q.push(Dat[i].T), total += Dat[i].T, Ans++;
        else if(Dat[i].T < Q.top()) {
                total -= Q.top(), Q.pop();
                Q.push(Dat[i].T), total += Dat[i].T;
            }
    printf("%d\n", Ans);
}

int main() {
    Input();
    Solve();
    return 0;
}