2051.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2051 on 2005-11-09 at 16:30:41 */ 
#include <cstdio>
#include <cstdlib>

const int MAX = 10240;

class Heap {
private:
	int size;
	int d[MAX];
	void siftUp(int n) {
		int dn = d[n];
		int i = n;
		while(i > 0 && dn > d[(i-1)/2]) {
			d[i] = d[(i-1)/2];
			i = (i - 1) / 2;
		}
		d[i] = dn;
	}
	void siftDown(int n) {
		int dn = d[n];
		int i = n;
		while(2 * i + 2 <= size) {
			int m = 2 * i + 1;
			if(dn < d[m] || (dn < d[m+1] && m + 2 <= size)) {
				if(m + 2 <= size && d[m] < d[m+1]) {
					m++;
				}
				d[i] = d[m];
				i = m;
			} else {
				break;
			}
		}
		d[i] = dn;
	}
public:
	void init() {
		size = 0;
	}
	bool isEmpty() {
		if(size == 0) {
			return true;
		} else {
			return false;
		}
	}
	void push(int n) {
		d[size] = n;
		siftUp(size);
		size++;
	}
	int pop() {
		int b = d[0];
		d[0] = d[--size];
		siftDown(0);
		return b;
	}
};

class Stop {
public:
	int L;
	int P;
};

int cmp(const void*, const void*);

int main()
{
    Stop stop[MAX];
	int n, i, L, P, nStop;
	Heap heap;
	bool can;
	
	while(scanf("%d", &n) == 1) {
		for(i = 0; i < n; i++) {
			scanf("%d %d", &stop[i].L, &stop[i].P);
		}
		stop[n].L = stop[n].P = 0;
		scanf("%d %d", &L, &P);
		qsort(stop, n+1, sizeof(Stop), cmp);
		can = true;
		nStop = 0;
		heap.init();
		for(i = 0; i <= n; i++) {
			if(P >= L - stop[i].L) {
				heap.push(stop[i].P);
				P -= L - stop[i].L;
				L = stop[i].L;
			} else {
				while(P < L - stop[i].L) {
					if(heap.isEmpty()) {
						can = false;
						break;
					} else {
						P += heap.pop();
						nStop++;
					}
				}
				if(!can) {
					break;
				} else {
					heap.push(stop[i].P);
					P -= L - stop[i].L;
					L = stop[i].L;
				}
			}
		}
		if(!can) {
			printf("-1\n");
		} else {
			printf("%d\n", nStop);
		}
	}
    
    return 0;
}

int cmp(const void *a, const void *b)
{
	Stop *x = (Stop*)a, *y = (Stop*)b;
    if(x->L > y->L) {
        return -1;
    } else {
        return 1;
    }
}