P4053 [JSOI2007]建筑抢修

首先按照结束时间排序,显然结束早的要去做。能做就做,如果做不了,就在前面找一个耗时最大的,把最大的扔掉,换成当前的,如果最大的也比当前的小,那么显然当前的是做不了的,不用管了.

struct inter {
	int r, len;
	bool operator <(const inter&rhs)const {
		return r < rhs.r;
	}
} t[N];
std::priority_queue<int> q;


int main() {
	read(n);
	rep(i, 1, n) {
		read(t[i].len);
		read(t[i].r);
	}
	std::sort(t + 1, t + n + 1);
	int last(0), ans(0);
	rep(i, 1, n) {
		if(last + t[i].len > t[i].r) {
			if(t[i].len < q.top()) {
				last -= q.top();
				last+=t[i].len;
				q.pop();
				q.push(t[i].len);
			}

		} else {
			last += t[i].len;
			++ans;
			q.push(t[i].len);
		}
	}


	out(ans, '\n');
	return 0;
}
上一篇:21.10.17模拟 桥牌


下一篇:Educational Codeforces Round 115 (Rated for Div. 2) 部分简要题解