3216728_ac_32ms_268k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, l, p;
struct node
{
    int dis;
    int fuel;
	bool operator < (const node &x) const 
	{
		return dis < x.dis;
	}
}ps[10001];

int r, heap[10001];

bool cmp(int a,int b)
{
	return ps[a].fuel < ps[b].fuel;
}

int main()
{
	int i, j, cnt;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%d%d",&ps[i].dis,&ps[i].fuel);
	}
	scanf("%d%d",&l,&p);
	r = 0;
	for(i = 0; i < n; i++)
	{
		ps[i].dis = l-ps[i].dis;
	}
	sort(ps,ps+n);
	cnt = 0;
	for(i = 0; i < n; i++)
	{
		j = i;
		while(j<n&&ps[j].dis <= p)
		{
			heap[r++] = j++;
			push_heap(heap,heap+r,cmp);
		}
		i = j-1;
		if(p >= l)
			break;
		else
		{
			if(r > 0)
			{
				p += ps[heap[0]].fuel;
				cnt++;
				pop_heap(heap,heap+r,cmp);
				r--;
			}
			else
				break;
		}
	}
	if(p < l)
		cnt = -1;
	printf("%d\n",cnt);
    return 0;
}