JSOI2007 建筑抢修

首先我们先按照报废时间排序,然后判断在鬼ID那个时间里能不能修好,如果修不好就炸掉

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define maxn 250000
#define int long long
#define rep(x,y,z) for(int x = y ; x <= z ;x ++) 
using namespace std ;
int n ;
struct dy{
	int  w , t ;
	int operator < (const dy &x) const {
		return t < x.t ;
	}
}a[maxn] ;
int tot , ans ;
priority_queue<int>q ;
signed main() {
	scanf("%lld",&n) ;
	rep(i,1,n) {
		scanf("%lld%lld",&a[i].w,&a[i].t) ;
	}sort(a+1,a+1+n) ;
	rep(i,1,n){
		if(tot + a[i].w > a[i].t) {
			if(a[i].w < q.top()) {
				tot -= q.top() , q.pop() ;
				q.push(a[i].w) ;
				tot += a[i].w ;
			}
		}else {
			ans ++ ;
			q.push(a[i].w) ;
			tot += a[i].w ;
		}
	}
	cout << ans << endl ;
	return 0 ;
}