BZOJ 1029: [JSOI 2007] 건축 응급 수리 우선 대기 열

1029: [JSOI 2007] 건축 응급 수리
Time Limit: 4 Sec  Memory Limit: 162 MB
제목 연결
http://www.lydsy.com/JudgeOnline/problem.php?id=1029
Description
샤 오강 은 JSOI 가 제공 하 는 '건축 응급 수리' 라 는 컴퓨터 게임 을 하고 있다. 치열 한 전 투 를 통 해 T 부락 은 모든 z 부락의 침입 자 를 소멸 했다.그러나 T 부락의 기지 에는 이미 N 개의 건축 시설 이 심각 한 손상 을 입 었 기 때문에 빨리 복구 하지 않 으 면 이 건축 시설 들 은 완전히 훼손 될 것 이다.현재 의 상황 은 T 부락 기지 에 수리 공이 한 명 밖 에 없다 는 것 이다. 비록 그 는 어느 건물 에 도 순간 도착 할 수 있 지만 모든 건물 을 복원 하 는 데 시간 이 필요 하 다.또 수리 공 은 한 건물 을 수리 해 야 다음 건물 을 수리 할 수 있 고 여러 건물 을 동시에 수리 할 수 없다.만약 어떤 건물 이 한동안 완전히 수리 되 지 않 았 다 면 이 건물 은 폐기 되 었 을 것 이다.당신 의 임 무 는 가능 한 한 많은 건물 을 서둘러 수리 할 수 있 도록 강 군 을 도와 수리 순 서 를 합 리 적 으로 제정 하 는 것 입 니 다.
Input
첫 번 째 줄 은 하나의 정수 N 이 고 그 다음 에 N 줄 은 두 개의 정수 T1 이 며 T2 는 하나의 건축 을 묘사 했다. 이 건축 을 수리 하 는 데 T1 초가 필요 하 다. 만약 에 T2 초 안에 수리 가 완성 되 지 않 으 면 이 건축 은 폐기 된다.
Output
정수 S 를 출력 하면 최대 S 개의 건물 을 서둘러 수리 할 수 있다 는 뜻 이다.데이터 범위: N < 150000, T1
Sample Input
4 100 200 200 1300 1000 1250 2000 3200
Sample Output
3
HINT
문제 풀이:
일단 종료 시간 에 맞 춰 서 정렬 을 해 볼 게 요.
하나의 큰 뿌리 로 가능 한 일 을 모두 던 져 라. 만약 한 가지 일이 안 될 때 가 있다 면 우 리 는 이 일이 걸 린 시간 을 큰 뿌리 로 쌓 인 첫 번 째 와 비교 해 보 자.
만약 그 보다 시간 을 적 게 소모 한다 면, 반드시 그 일 을 대체 할 수 있 을 것 이다.
증명 은 그래도 매우 간단 하 니, 생각해 보면 알 수 있다.
코드:
 

//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 200001 #define mod 10007 #define eps 1e-9 //const int inf=0x7fffffff; //    const int inf=0x3f3f3f3f; /* */ //**************************************************************************************  inline ll read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct node { int x,y; }; bool cmp(node a,node b) { return a.y<b.y; } node a[maxn]; priority_queue<int> q; int main() { int n; cin>>n; for(int i=0;i<n;i++) a[i].x=read(),a[i].y=read(); sort(a,a+n,cmp); int now=0; int ans=0; for(int i=0;i<n;i++) { if(now+a[i].x<=a[i].y) { ans++; now+=a[i].x; q.push(a[i].x); } else { int h=q.top(); if(a[i].x<h) { q.pop(); q.push(a[i].x); now=now+a[i].x-h; } } } cout<<ans<<endl; }