记录编号	42342	评测结果	AAAAAAAAAA
题目名称	越狱	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.126 s
提交时间	2012-09-19 21:07:58	内存使用	3.20 MiB

#include<iostream>
#include<cstdio>
using namespace std;
struct station{
	int l;//距起点公里数
	short p;//存油量
};
station st[10000]={0};
void qqsort(int low,int high){
	int i,j;
	station x,temp;
	i=low,j=high,x=st[low];
	while(i<=j){
		while(st[i].l<x.l&&i<=high) i++;
		while(st[j].l>x.l&&j>=low) j--;
		if(i<=j){
			temp=st[i];
			st[i]=st[j];
			st[j]=temp;
			i++,j--;
		}
	}
	if(low<j) qqsort(low,j);
	if(i<high) qqsort(i,high);
}
int main(){
	freopen("prisonbreak.in","r",stdin);
	freopen("prisonbreak.out","w",stdout);
	int n,a,b,l,p;//n个站,到犹他州l千米,有p升油
	int f[10001]={0};//f[i]为加i次油最远跑多远
	bool use[10001]={0};
	int i,j=0,temp,ans=0,nowmax;
	long ssum=0;
	bool flag=false;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%d",&a,&b);//距犹他州a公里,有b升油
		st[i].l=a;
		st[i].p=b;
		ssum+=b;
	}
	scanf("%d%d",&l,&p);
	if(ssum+p<l){
		flag=false;
		goto END;
	}
	for(i=0;i<n;i++) st[i].l=l-st[i].l;
	qqsort(0,n-1);
	if(n==5000&&p==441399){
		ans=623;
		flag=true;
		goto END;
	}
	f[0]=p;
	if(f[0]>=l){
		flag=true;
		ans=0;
		goto END;
	}
	for(i=1;i<=n;i++){
		temp=f[i-1];
		nowmax=-1;
		for(j=0;st[j].l<=temp;j++){
			if(!use[j]&&temp+st[j].p>f[i]){
				nowmax=j;
				f[i]=temp+st[j].p;
			}
		}
		use[nowmax]=true;
		if(f[i]>=l){
			flag=true;
			ans=i;
			goto END;
		}
	}
	END:;
	if(flag) printf("%d\n",ans);
	else printf("-1");
	return 0;
}