pku2431.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 91 行

#include <stdio.h>
#include <algorithm>
using namespace std;

typedef struct Node
{
	int d, f;
} Node;

const int size = 11000;
int heap[size];
Node v[size];
int heap_size;
int N, P, L;

bool cmp(const Node &a, const Node &b)
{
	return a.d < b.d;
}

bool heap_cmp(int x, int y)
{
	return x < y;
}

void Add(int x)
{
	heap[heap_size++] = x;
	push_heap(heap, heap + heap_size, heap_cmp);
}

int Remove()
{
	int ans = heap[0];
	pop_heap(heap, heap + heap_size, heap_cmp);
	heap_size--;
	return ans;
}

int Solve()
{
	int i, sum, cnt;
	sum = 0;
	heap_size = 0;
	for (i = 0; i < N; i++)
	{
		scanf("%d %d", &v[i].d, &v[i].f);
	}
	scanf("%d %d", &L, &P);
	for (i = 0; i < N; i++)
	{
		v[i].d = L - v[i].d;
	}
	v[N].d = L;
	v[N].f = 0;
	N++;
	sort(v, v + N, cmp);
	sum = P;
	for (i = 0; i < N; i++)
	{
		if (v[i].d <= sum)
			Add(v[i].f);
		else
			break;
	}
	cnt = 0;
	while (i < N)
	{
		if (v[i].d <= sum)
		{
			Add(v[i++].f);
		}
		else
		{
			if (heap_size == 0)
				break;
			sum += Remove();
			cnt++;
		}
	}
	return i == N ? cnt : -1;
}

int main()
{
	while (EOF != scanf("%d", &N))
		printf("%d\n", Solve());
	return 0;
}